189. 轮转数组
type
status
date
slug
summary
tags
category
difficulty
icon
password
189. 轮转数组
给定一个整数数组
nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。示例 1:
示例 2:
提示：
1 <= nums.length <= 105
231 <= nums[i] <= 231 - 1
0 <= k <= 105
解题思路：
本题使用三次翻转法来解决数组轮转问题。这种方法的时间复杂度为O(n)，空间复杂度为O(1)。以下是具体解析：
算法步骤
- 首先处理k值：由于k可能大于数组长度，我们需要用k对数组长度n取模，即k = k % n
- 对整个数组进行翻转
- 对前k个元素进行翻转
- 对剩余的n-k个元素进行翻转
举例说明
以示例1为例，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)，其中n是数组的长度。每次翻转操作的时间复杂度为O(n)
- 空间复杂度：O(1)，只使用了常数级别的额外空间
代码细节
代码中使用了C++ STL中的reverse函数，它可以在指定的范围内原地翻转元素。reverse函数有三次调用：
- 第一次reverse(nums.begin(), nums.end())翻转整个数组
- 第二次reverse(nums.begin(), nums.begin() + k)翻转前k个元素
- 第三次reverse(nums.begin() + k, nums.end())翻转剩余元素
这种解法的优点是不需要使用额外的空间，所有操作都是在原数组上进行的，非常适合处理大规模数据的情况。
- 作者:Episkey
- 链接:https://episkey.top/article/rotate-array
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
