当前位置：首页 > news >正文

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

news 2025/8/14 0:29:27

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

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

漫漫长路，才刚刚开始…

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

参考文章:

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

文章目录

- - 代码训练(19)LeetCode之轮转数组
  - - 1. 原题
    - 2. 分析
    - 3. 代码实现
    - 4. 总结

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. 分析

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

方法一：使用额外数组

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

方法二：多次反转

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

方法三：环状替换

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

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

反转整个数组：[7,6,5,4,3,2,1]
反转前 k 个元素：[5,6,7,4,3,2,1]
反转剩余元素：[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个位置；输出旋转后的结果。

算法复杂度：