leetcode 189 题解
编程：vector数组翻转

题目

给定一个整数数组 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
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> new_nums(n);
        for(int i=0;i<n;i++) {
            new_nums[(i+k)%n]=nums[i];
        }
        nums=new_nums;
        return;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

数学解法：原地解法

不使用额外的数组，直接交换原位置和新位置的数。假设从nums[0]开始交换，令temp=nums[0]，nums[0]的新位置就是$x = (0+k) mod n$，故交换temp与nums[x]，接下来处理原$x$处的数据，新的位置是$y = (x+k) mod n$，所以交换temp与nums[y]。如此循环，最后会回到0。

数学证明如下：

  1. 定义迭代函数：
    定义函数 $f(x) = (x + k) \mod n$

  2. 观察周期性：
    因为 $n$ 是模数，所以所有可能的结果（$x$ 的值）都在集合 ${0, 1, 2, …, n-1}$ 中。这个集合中有 $n$ 个元素。

  3. 迭代次数：
    通过重复应用函数 $f$，我们得到一个序列 $x, f(x), f(f(x)), \ldots$。由于集合 ${0, 1, 2, …, n-1}$ 是有限的，根据鸽巢原理，至少有一个元素在经过多次迭代后会重复出现。这意味着存在整数 $m$ 和 $l$（$m \neq l$）使得 $f^m(x) = f^l(x)$。

  4. 周期的证明：
    假设 $f^m(x) = f^l(x)$，不妨设 $m > l$，我们有 $f^m(x) = f^l(x)$。这可以简化为 $f^{m-l}(x) = x$。意味着从 $x$ 开始的序列在 $m-l$ 次迭代后回到了 $x$。因此，该函数是周期性的，并且周期最多是 $n$。

证明了最后会回到0之后，我们就需要判断应该迭代多少次，才能覆盖整个数组。因为开始时是nums[0]，最后同样回到nums[0]，刚好走了整数次的数列，设这个数为 $a$ ，再设这个过程总共遍历了 $b$ 个数，我们可以得出 $an=bk$ 。因为 $b$ 是我们需要求的值，而 $n$ 是固定的，所以 $an$ 由 $a$ 和 $k$ 决定。因为只需要遍历一次，所以 $a$ 需要尽可能的小，所以 $an$ 是 $a$ 和 $k$ 的最小公倍数 $\text{lcm}(a,k)$ ，所以每次遍历的元素个数是 $b=\frac{\text{lcm}(a,k)}{k}$ 。

为了访问到所有的元素，我们需要进行遍历的次数为
$$\frac{n}{\text{lcm}(n,k)/k}=\frac{nk}{\text{lcm}(n,k)}=\text{gcd}(n,k)$$

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;
        int count = gcd(k, n);
        for (int start = 0; start < count; ++start) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % n;
                swap(nums[next], prev);
                current = next;
            } while (start != current);
        }
    }
};

一种更直接的解法是，直接使用一个变量count记录已经完成旋转的变量，当count等于数组大小时，终止循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int temp = 0, n = nums.size(), count = 0, index = 0, initialindex = 0;
        while (count < n) {
            index = initialindex;
            temp = nums[(index + k) % n];
            nums[(index + k) % n] = nums[index];
            index = (index + k) % n;
            count++;
            while (index != initialindex) {
                swap(nums[(index + k) % n], temp);
                index = (index + k) % n;
                count++;
            }
            initialindex++;
        }
        return;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

数组翻转

当我们将数组的元素向右移动 k 次后，尾部 k mod n 个元素会移动至数组头部，其余元素向后移动 k mod n 个位置。所以，我们可以先将所有元素翻转，这样尾部的 k mod n 个元素就被移至数组头部，然后我们再翻转 [0, k mod n−1] 区间的元素和 [k mod n, n−1] 区间的元素即能得到最后的答案。

我们以 n=7，k=3 为例进行如下展示：

环序 结果
原始数组 1 2 3 4 5 6 7
翻转所有元素 7 6 5 4 3 2 1
翻转 $[0, k \mod n - 1]$ 区间的元素 5 6 7 4 3 2 1
翻转 $[k \mod n, n - 1]$ 区间的元素 5 6 7 1 2 3 4 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void reverse(vector<int>& nums, int start, int end) {
        while (start < end) {
            swap(nums[start], nums[end]);
            start += 1;
            end -= 1;
        }
    }

    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1);
    }
};
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。