面试经典150题 P189 轮转数组

---

时间轴

时间轴

2025-09-29

init

反转数组

---

题目：

P189 轮转数组

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

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

#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] 区间的元素即能得到最后的答案。

#include <algorithm>
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();

        k %= n;

        std::reverse(nums.begin(), nums.begin() + n - k);
        std::reverse(nums.begin() + n - k, nums.end());
        std::reverse(nums.begin(), nums.end());

    }
};

leetcode hot 100 rewrite

#include <vector>
#include <algorithm>

using std::vector;

class Solution {
    public:
        void rotate(vector<int> &nums, int k)
        {
                int n = nums.size();

                k = k % n;

                std::reverse(nums.begin(), nums.begin() + n - k);
                std::reverse(nums.begin() + n - k, nums.end());
                std::reverse(nums.begin(), nums.end());
        }
};