旋转数组

发表于 | 分类于 | 浏览 次
  1. Rotate Array
    旋转数组

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

1
2
3
4
5
6
Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

1
2
3
4
5
Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Note:

  • Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
  • Could you do it in-place with O(1) extra space?

方法一：暴力破解

方法二：使用额外空间

方法三：循环移动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void rotate(vector<int> &nums, int k) {
    k = k % nums.size();
    int count = 0;
    for (int start = 0; count < nums.size(); start++) {
        int current = start;
        int prev = nums[start];

        // 如果移动的数量正好等于nums.size()时，每个元素移动后的位置都是移动前的位置
        // 那么这个循环的唯一目的就是为了count++
        // nums: [0,1,2,3], k=4
        do {
            int next = (current + k) % nums.size();
            int temp = nums[next];
            nums[next] = prev;
            prev = temp;
            current = next;
            count++;
        } while (start != current);
    }
}

具体过程
[0,1,2,3,4,5,6] , k = 3时，
start = 0, 0-3,3-6,6-2, 2-5, 5-1, 1-4, 4-0，此时count=7，start=0，current = 0, 故退出内层循环
退出内层循环，又因为count==nums.size()，故退出外层循环．
[0,1,2,3,4,5], k = 2时，
start = 0, 0-2, 2-4, 4-0, current = 0, start = 0, count = 3,故退出内层循环．
start = 1, 1-3, 3- 5, 5 - 1, current = 1, start = 1,　故退出内层循环．count = 6, 故退出外层循环．

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

方法四：数组逆转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void reverse(vector<int> &nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        ++start, --end;
    }
}

void rotate1(vector<int> &nums, int k) {
    k = k % nums.size();
    reverse(nums, 0, nums.size() - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.size() - 1);
}