LeetCode Hot100刷题——轮转数组

56. 轮转数组

给定一个整数数组 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]

提示：

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

解题思路

我的思路：每次轮转其实就是把最后的元素放到前面，那总的结果就是相当于整个数组后k个元素被移动到前面，剩下的元素顺次后移。再考虑到假如当k等于数组长度的时候，轮转k次相当于没有轮转。所以这个时候需要优化k的值，例如数组长度n=7，k=10，k%n=10%7=3，即只需要轮转3次即可就可以避免不必要的重复操作。

如何高效地将数组轮转k次

方法一：使用额外的数组

创建一个新数组，将原数组的后k个元素放到新数组的前面，然后把原数组前面的元素放到后面。例如，原数组nums，新数组的0到k-1位置是nums的n-k到n-1的元素，k到n-1的位置是nums的0到n-k-1的元素。这种方法的时间复杂度是O(n)，空间复杂度是O(n)。

方法二：三次反转

假设k=3，数组是1,2,3,4,5,6,7。整个数组反转之后变成7,6,5,4,3,2,1。然后将前k个元素反转，再反转剩下的元素。比如前3个元素反转后是5,6,7，剩下的反转是1,2,3,4。这样整个数组就是5,6,7,1,2,3,4。这三次反转的结果就是轮转后的数组。因为反转操作是原地进行的，时间复杂度是O(n)，空间复杂度是O(1)，更加高效。

代码实现具体步骤：

1. 计算数组的长度n
2. 处理k的值：首先对k取模数组长度n，k = k % n，避免不必要的重复轮转。如果k为0，直接返回。
3. 反转整个数组
4. 反转前k个元素
5. 反转剩下的n - k 个元素

反转数组的部分写一个辅助函数表示用来反转数组的一部分，比如从start到end的位置。reverse(nums, start, end)这个函数会将nums数组中从start到end（包括这两个位置）的元素反转。

比如，反转整个数组的话，调用reverse(nums, 0, n-1)。然后反转前k个元素，调用reverse(nums, 0, k-1)。然后反转剩下的部分，调用reverse(nums, k, n-1)。

经过三次反转后，数组就正确了。

程序代码

class Solution {public void rotate(int[] nums, int k) {// 获取数组长度int n = nums.length;// 数组为空，直接返回if(n == 0){return;}// 取模处理k大于数组长度的情况，避免无效重复轮转k = k % n;// k为0，说明无需轮转，直接返回即可if(k == 0){return;}// 反转整个数组reverse(nums, 0, n - 1);// 反转前k个元素reverse(nums, 0, k - 1);// 反转剩余元素reverse(nums, k, n - 1);}private void reverse(int[] nums, int start, int end){while(start < end){int temp = nums[start];nums[start] = nums[end];nums[end] = temp;start++;end--;}}
}

示例分析：

1. 预处理：

   • 数组长度n = 7，k = 3 % 7 = 3。

2. 三次反转：

   • 第一次反转：反转整个数组[1, 2, 3, 4, 5, 6, 7] → [7, 6, 5, 4, 3, 2, 1]。
   • 第二次反转：反转前 3 个元素[7, 6, 5] → [5, 6, 7]，数组变为[5, 6, 7, 4, 3, 2, 1]。
   • 第三次反转：反转剩余 4 个元素[4, 3, 2, 1] → [1, 2, 3, 4]，数组变为[5, 6, 7, 1, 2, 3, 4]。

时间复杂度分析：

• 时间复杂度：O (n)。三次反转操作每次都遍历数组的一部分，总时间复杂度为线性。
• 空间复杂度：O (1)。只使用了常数级的额外空间，无需创建新数组。