LeetCode - 解题笔记 - 189 - Rotate Array

Solution 1

题目中希望本题至少实现三种方法，其中一种就是直接暴力地使用一个额外的新数组保存临时结果，因此不表。

对上述方式进一步简化，我们可以通过一个状态变量来保存转换结果但是很快发现经过一定次数后，调换会形成一个循环，并且经过观察发现一共有 gcd(k,n)个这样的循环。

• 时间复杂度：$O(N)$，其中$N$为输入数组的长度。所有的数字都要完成一次旋转，因此先行遍历一次
• 空间复杂度： $O(1)$，仅需要常数个状态量维护整个旋转过程

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        // 首先确定总的遍历起始偏移量：gcd(k, n)
        int len = nums.size();
        int offset = gcd(k, len);
        
        // 逐个循环的遍历完成旋转
        for (int i = 0; i < offset; ++i) {
            int temp = i;
            int tempVal = nums[temp];
            do {
                int next = (temp + k) % len;
                swap(nums[next], tempVal);
                temp = next;
            } while (temp != i);
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Solution 2

【参考官方题解】

一个简单的但有意思的规律：

给定指定的旋转量k，那么可以通过翻转整个数组→按照 k mod n 进行切分分别进行翻转完成旋转。需要做的就是实现一个in-place的翻转函数。

• 时间复杂度：$O(N)$，其中$N$为输入数组的长度。所有的数字都要完成两次翻转
• 空间复杂度： $O(1)$，仅需要常数个状态量维护整个翻转过程

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int len = nums.size();
        int offset = k % len;
        // cout << offset << endl;
        
        reverse(nums, 0, len - 1);
        reverse(nums, 0, offset - 1);
        reverse(nums, offset, len - 1);
    }
    
private:
    void reverse(vector<int> & nums, int start, int end) {
        while (start < end) {
            swap(nums[start], nums[end]);
            start++;
            end--;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Solution 3

Solution 1的Python实现

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        length = len(nums)
        offset = gcd(k, length)
        
        for i in range(offset):
            temp, tempVal = i, nums[i]
            # print(temp, tempVal)
            while True:
                new = (temp + k) % length
                nums[new], tempVal = tempVal, nums[new]
                temp = new
                # print(temp)
                if temp == i: break
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Solution 4

Solution 2的Python实现

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def reverse(start, end):
            nonlocal nums
            while start < end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1
                
        length = len(nums)
        offset = k % length
        
        reverse(0, length - 1)
        reverse(0, offset - 1)
        reverse(offset, length - 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18