【练习】力扣 热题100 轮转数组

题目 轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:
输入： nums = [-1,-100,3,99], k = 2
输出： [3,99,-1,-100]
解释: 向右轮转 1步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100]

来源：力扣 热题100 轮转数组

题解

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if(nums.size() == 1)
            return;
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k % nums.size());
        reverse(nums.begin() + k % nums.size(), nums.end());
        return;
    }
};

代码分析：

1. 检查数组是否只有一个元素：

   if(nums.size() == 1)
       return;
   

   如果数组的长度为1，那么无论旋转多少次，数组都不会改变，因此直接返回。

2. 反转整个数组：

   reverse(nums.begin(), nums.end());
   

   将整个数组反转。例如，如果数组是 [1, 2, 3, 4, 5]，反转后变为 [5, 4, 3, 2, 1]。

3. 反转前 k % nums.size() 个元素：

   reverse(nums.begin(), nums.begin() + k % nums.size());
   

   反转数组的前 k % nums.size() 个元素。这里使用 k % nums.size() 是为了处理 k 大于数组长度的情况。例如，如果 k = 2，数组是 [5, 4, 3, 2, 1]，反转前2个元素后变为 [4, 5, 3, 2, 1]。

4. 反转剩余的元素：

   reverse(nums.begin() + k % nums.size(), nums.end());
   

   反转从第 k % nums.size() 个元素到数组末尾的部分。继续上面的例子，剩余的元素 [3, 2, 1] 反转后变为 [1, 2, 3]，最终数组为 [4, 5, 1, 2, 3]。

举例说明：

假设输入数组为 nums = [1, 2, 3, 4, 5]，k = 2，运行过程如下：

1. 反转整个数组：

   • 原数组：[1, 2, 3, 4, 5]
   • 反转后：[5, 4, 3, 2, 1]

2. 反转前 k % nums.size() 个元素：

   • k % nums.size() = 2 % 5 = 2
   • 反转前2个元素：[4, 5, 3, 2, 1]

3. 反转剩余的元素：

   • 剩余元素：[3, 2, 1]
   • 反转后：[1, 2, 3]
   • 最终数组：[4, 5, 1, 2, 3]

输出结果为 [4, 5, 1, 2, 3]，即数组向右旋转了2步。

时间复杂度：

• O(n)，其中 n 是数组的长度。因为每个元素被反转了两次（整体反转和部分反转），但总的操作次数仍然是线性的。

空间复杂度：

• O(1)，因为没有使用额外的空间，所有操作都是在原数组上进行的。

总结：

这段代码通过三次反转操作实现了数组的旋转，是一种非常高效且简洁的实现方式。它的核心思想是通过反转来重新排列数组元素，避免了使用额外的空间，同时保证了线性的时间复杂度。