时间轴

2025-09-29

init

题目：

P189 轮转数组

https://leetcode.cn/problems/rotate-array/description/?envType=study-plan-v2&envId=top-interview-150

用额外数组的方式。这种方法时间复杂度在 O(n)，但是开辟额外数组也会花时间空间复杂度也是 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <vector>

using std::vector;

class Solution {
public:
  void rotate(vector<int> &nums, int k) {
    int n;
    int tmp;
    int pos;

    n = nums.size();
    vector<int> vec(n);

    for (int i = 0; i < n; i++) {
      pos = (i + k) % n;
      vec[pos] = nums[i];
    }
    nums = std::move(vec);
  }
};

另一种巧妙的方式：
我们将数组的元素向右移动 k 次后，尾部k mod n个元素会移动至数组头部，其余元素向后移动 kmodn 个位置。

该方法为数组的翻转：我们可以先将所有元素翻转，这样尾部的k mod n个元素就被移至数组头部，然后我们再翻转 [0,k mod n−1] 区间的元素和 [k mod n,n−1] 区间的元素即能得到最后的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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);
    }
};