By Ne0 — May 20, 2024

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，其具体流程如下所示：
↓ ← ← ← ← ← ↑ ↓ ↑ 1 ‾ 2 3 4 ‾ 5 6 7 ‾ 8 9 ↓ ↑ ↓ ↑ ↓ → → ↑ ↓ → → ↑ \begin{array}{l} \downarrow\hspace{0.8em} \leftarrow \hspace{0.6em} \leftarrow \hspace{0.6em} \leftarrow \hspace{0.5em} \leftarrow \hspace{0.5em} \leftarrow \hspace{0.8em} \uparrow \hspace{1.5em} \hspace{1.5em} \\ \downarrow\hspace{1.3em} \hspace{1.3em} \hspace{1.2em} \hspace{2.4em} \hspace{1.3em} \hspace{1.3em} \uparrow \hspace{1.5em} \hspace{1.5em} \\ \underline{\bold{1}} \hspace{1em} 2 \hspace{1em} 3 \hspace{1em} \underline{\bold{4}} \hspace{0.9em} 5 \hspace{1em} 6 \hspace{1em} \underline{\bold{7}} \hspace{0.9em} 8 \hspace{1em} 9 \\ \downarrow\hspace{1.3em} \hspace{1.3em} \hspace{1.4em} \uparrow\downarrow \hspace{1.1em} \hspace{1.3em} \hspace{1.4em} \uparrow \hspace{1.5em} \hspace{1.5em} \\ \downarrow\hspace{0.8em} \rightarrow \hspace{0.7em} \rightarrow \hspace{0.5em} \uparrow\downarrow \hspace{0.6em} \rightarrow \hspace{0.5em} \rightarrow \hspace{0.7em} \uparrow \hspace{1.5em} \hspace{1.5em} \\ \end{array}↓←←←←←↑↓↑123456789↓↑↓↑↓→→↑↓→→↑

记 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 时，表示循环遍历完成，进行特殊处理：

对起点位置进行赋值，即 nums[start] = val
进行下一组的移动，将 start++，且更新 i，即 i = start
更新 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 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;
        }
    }
}