代码训练LeetCode(19)轮转数组

代码训练(19)LeetCode之轮转数组

Author: Once Day Date: 2025年6月3日

漫漫长路，才刚刚开始…

全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客

参考文章:

• 189. 轮转数组 - 力扣（LeetCode）
• 力扣 (LeetCode) 全球极客挚爱的技术成长平台

1. 原题

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

提示：

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

示例 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]

2. 分析

解决这个问题有多种方法，以下是三种主要的方法：

方法一：使用额外数组

1. 创建一个新的数组来存储移动后的结果。
2. 对于 nums 中的每个元素，计算它移动后的新位置 (i + k) % n （其中 i 是当前索引，n 是数组长度），并将其放到新数组对应位置。
3. 将新数组复制回原数组。

方法二：多次反转

1. 当 k 大于数组长度时，只需要移动 k % n 次（因为每 n 次移动都会让数组恢复原状）。
2. 反转整个数组。
3. 反转数组的前 k 个元素。
4. 反转数组剩余的部分。

方法三：环状替换

1. 从数组的第一个元素开始，将当前元素放到正确的新位置。
2. 从新位置继续执行相同的替换过程，直到回到起始位置。
3. 如果数组长度是 k 的倍数，在完成一个循环后，需要从下一个位置开始新的循环，直到遍历完所有元素。

假设 nums = [1,2,3,4,5,6,7]，k = 3。使用方法二（多次反转）：

1. 反转整个数组：[7,6,5,4,3,2,1]
2. 反转前 k 个元素：[5,6,7,4,3,2,1]
3. 反转剩余元素：[5,6,7,1,2,3,4]

性能优化关键点

• 空间复杂度：方法一需要 O(n) 的额外空间，而方法二和三可以实现 O(1) 的空间复杂度。
• 时间复杂度：所有方法的时间复杂度都为 O(n)。
• 原地算法：方法二和三是原地算法，不需要使用额外的数组空间。

3. 代码实现

#include <stdio.h>void reverse(int* nums, int start, int end) {while (start < end) {int temp = nums[start];nums[start] = nums[end];nums[end] = temp;start++;end--;}
}void rotate(int* nums, int numsSize, int k) {k = k % numsSize;reverse(nums, 0, numsSize - 1);reverse(nums, 0, k - 1);reverse(nums, k, numsSize - 1);
}int main() {int nums[] = {1, 2, 3, 4, 5, 6, 7};int k = 3;int n = sizeof(nums) / sizeof(nums[0]);rotate(nums, n, k);for (int i = 0; i < n; i++) {printf("%d ", nums[i]);}return 0;
}

这段代码实现了数组旋转算法，具体分析如下：

• reverse函数：实现数组指定区间内元素的反转，通过交换首尾元素实现。
• rotate函数：将数组向右旋转k个位置，采用了"三次反转"的高效方法：首先取k对数组大小求余，处理k大于数组长度的情况；将整个数组反转，再反转前k个元素；最后反转剩余元素。
• main函数：定义一个样例数组{1,2,3,4,5,6,7}；将其右旋转3个位置；输出旋转后的结果。

算法复杂度：

• 时间复杂度：O(n)，其中n是数组长度
• 空间复杂度：O(1)，原地操作，不需要额外空间

这是一个巧妙的旋转算法，避免了使用额外的数组空间，通过三次反转操作高效完成旋转任务。

4. 总结

这个题目考查了数组操作和算法设计的能力，特别是如何高效地在数组上进行位置调整。通过不同方法的比较，我们可以学到多种解决问题的方式，并理解原地算法的重要性和实现方式。对于提升编程能力，重要的是多练习、多思考不同的解决方案以及它们的优缺点。