C 语言第39题：数组左移 k 位（循环移位）

题目

数组左移 k 位（循环移位）

思路

本题把数组循环左移 k 位（末尾元素移到前面）。

先令 k %= n 避免无效旋转。可开辅助数组：b[i]=a[(i+k)%n]；或用三次反转法：[0,k)、[k,n) 各自反转再整体反转。k==0 时不变。

解题分析

左移 k 位等于把前 k 个元素搬到尾部。用临时数组存前 k 个再拼接，好理解；三次反转（整段、前 k、后 n-k）可以在 O(1) 额外空间完成，k 要先对 n 取模。

完整程序

#include <stdio.h>

int main(void)
{
    int n, k, a[500], tmp[500];
    if (scanf("%d %d", &n, &k) != 2 || n < 1) {
        return 1;
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    k %= n;
    for (int i = 0; i < k; i++) {
        tmp[i] = a[i];
    }
    for (int i = 0; i < n - k; i++) {
        a[i] = a[i + k];
    }
    for (int i = 0; i < k; i++) {
        a[n - k + i] = tmp[i];
    }
    for (int i = 0; i < n; i++) {
        printf("%d%c", a[i], i + 1 < n ? ' ' : '\n');
    }
    return 0;
}

运行示例

输入：

5 2
1 2 3 4 5

输出：

3 4 5 1 2

其它写法

下面每种写法都是完整程序，输入输出格式与正文一致，便于对照。

三次反转

程序：

#include <stdio.h>

static void reverse(int *a, int l, int r)
{
    while (l < r) {
        int t = a[l];
        a[l] = a[r];
        a[r] = t;
        l++;
        r--;
    }
}

int main(void)
{
    int n, k, a[500];
    if (scanf("%d %d", &n, &k) != 2 || n < 1) {
        return 1;
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    k %= n;
    reverse(a, 0, n - 1);
    reverse(a, 0, k - 1);
    reverse(a, k, n - 1);
    for (int i = 0; i < n; i++) {
        printf("%d%c", a[i], i + 1 < n ? ' ' : '\n');
    }
    return 0;
}

运行示例

输入：

5 2
1 2 3 4 5

输出：

3 4 5 1 2