LeetCode 189. 轮转数组
题目描述
思路分析
三次翻转：先翻转集合的左右两部分，然后翻转整个集合。
- 先反转整个数组。
- 然后反转前 k 个元素。
- 最后反转剩余的 n-k 个元素。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func rotate(nums []int, k int) {
n := len(nums)
if n <= 0 {
return
}
k = k % n // 处理 k 大于 n 的情况
if k == 0 {
return
}
// 反转整个数组
reverse(nums, 0, n-1)
// 反转前 k 个元素
reverse(nums, 0, k-1)
// 反转剩余的 n-k 个元素
reverse(nums, k, n-1)
}
func reverse(nums []int, start int, end int) {
for start < end {
nums[start], nums[end] = nums[end], nums[start]
start++
end--
}
}
时间复杂度：O(n)，其中 n 是数组的长度。每个元素都被访问和反转一次。
空间复杂度：O(1)，只使用了常量级的额外空间。
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！