LeetCode 189. 轮转数组

一、题目

  给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入： nums = [-1,-100,3,99], k = 2
输出： [3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

进阶：

• 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
• 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

  点击此处跳转题目。

二、Java 题解

  自己拿到题目后的第一反应是将每个元素向前移动 k 个位置，直至遇到先前移动过的元素，则停止该组移动，进行下一组移动。
  例如，对于 length = 9 的数组，k = 3，其具体流程如下所示：
$$\begin{array}{l}\downarrow \leftarrow \leftarrow \leftarrow \leftarrow \leftarrow \uparrow \\ \downarrow \uparrow \\ \underline{1}23\underline{4}56\underline{7}89\\ \downarrow \uparrow \downarrow \uparrow \\ \downarrow \to \to \uparrow \downarrow \to \to \uparrow \end{array}$$

  记 length 和 k 的最大公约数为 round，因此在该例子中将数组分为 round = 3 组，上图表示第一组，即 [1, 4, 7]，为一个循环，其中每个数不断前进 k 个位置，最终会无限循环下去。每一组的起点记为 start；使用 i 遍历，每次 + k；next 为下一个即将到达的位置，其值为 i + k；val 记录下一个位置的值，即 val = nums[next]；last 记录上一个位置的值，用于对下一个位置 next 进行赋值，last = val（上一次遗留下来的 val）。
  当 next == start 时，表示循环遍历完成，进行特殊处理：

1. 对起点位置进行赋值，即 nums[start] = val
2. 进行下一组的移动，将 start++，且更新 i，即 i = start
3. 更新 last，即 last = nums[i]

  最终所有组移动完毕，结束算法。

class Solution {
    public void rotate(int[] nums, int k) {
        if (k == 0) return;
        int n = nums.length, round = GCD(n, k);
        if (round == n) return;
        int i = 0, last = nums[i], val = nums[k % n], start = i, next;
        do {
            next = (i + k) % n;
            if (next == start) { // 循环结束，特殊处理
                nums[next] = val;
                i = ++start;
                last = nums[i];
                round--;
                continue;
            }
            // 将元素后移 k 个位置
            val = nums[next];
            nums[next] = last;
            last = val;
            i = next;
        } while (round > 0);
    }

    // 辗转相除法求解最大公约数
    public int GCD(int a, int b) {
        if (a < b) return GCD(b, a);
        if (a % b == 0) return b;
        return GCD(b, a % b);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

• 时间：1 ms，击败 62.24% 使用 Java 的用户
• 内存：52.65 MB，击败 83.18% 使用 Java 的用户

  当然，这道题的最优解还是翻转三次数组啦~

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        Reverse(nums, 0, nums.length);
        Reverse(nums, 0, k);
        Reverse(nums, k, nums.length);
    }

    // 翻转 [start, end) 区间
    public void Reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start++] = nums[--end];
            nums[end] = temp;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 时间：0 ms，击败 100.00% 使用 Java 的用户
• 内存：52.61 MB，击败 86.35% 使用 Java 的用户