rotateArray

189. 轮转数组

分析

确定实际轮转次数：
- 如果 k 大于数组长度 n，轮转后的结果与 k % n 次轮转相同
- 因此需要先对 k 取模：k %= n
三次反转法：
- 整体反转：将整个数组反转，这样后 k 个元素会移动到前面
- 前部分反转：将前 k 个元素反转，恢复它们的顺序
- 后部分反转：将剩余的 n-k 个元素反转，恢复它们的顺序

时间复杂度

反转操作：每次反转需要遍历部分数组，整体复杂度为 O(n)

空间复杂度

原地操作：仅使用常数级别的额外空间，空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution
{
public:
    void rotate(vector<int>& nums, int k)
    {
        int n = nums.size();
        k %= n;  // 计算有效的轮转次数

        // 反转整个数组
        for (int i = 0; i < n / 2; ++i)
            std::swap(nums[i], nums[n - 1 - i]);

        // 反转前 k 个元素
        for (int i = 0; i < k / 2; ++i)
            std::swap(nums[i], nums[k - 1 - i]);

        // 反转后 n-k 个元素
        for (int i = k; i < (n + k) / 2; ++i)
            std::swap(nums[i], nums[n - 1 - i + k]);
    }
};