Java第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 取模。

完整程序

import java.io.*;

public class Main {
    public static void main(String[] args) {
        int n = 5, k = 2;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = 1;
        k %= n;
        int[] tmp = new int[k];
        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++) System.out.print(a[i] + (i + 1 < n ? " " : "\n"));
    }
}

运行示例

输出：

3 4 5 1 2

其它写法

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

三次反转

程序：

public class Main {
    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--;
        }
    }
    public static void main(String[] args) {
        int n = 5, k = 2;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = 1;
        }
        k %= n;
        reverse(a, 0, n - 1);
        reverse(a, 0, k - 1);
        reverse(a, k, n - 1);
        for (int i = 0; i < n; i++) {
            System.out.print(a[i] + (i + 1 < n ? " " : "\n"));
        }
    }
}

运行示例

输出：

3 4 5 1 2