1.题目描述
给定一个整数数组
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个数组
2.1解题思路
题目要求将数组中的元素向右轮转 k
个位置,首先排除特殊情况,将长度等于一的数组返回,k值大于数组长度时将k值对数组长度取余,然后设置一个长度为k的切片,将当前数组最后面的k 个元素先存入到切片中去,然后将数组前面的 len(nums) - k 个元素依次向后面挪动k个位置,最后将切片中的 k 个元素放入到nums数组的前 k 个位置中,这样就实现了将数组中的元素向右轮转 k
个位置。
代码展示:
func rotate(nums []int, k int) {
n := len(nums)
if n == 0 {
return
}
k = k % n
temp := make([]int, k)
for i := 0; i < k; i++ {
temp[i] = nums[n - k + i]
}
for i := n - 1; i >= k; i-- {
nums[i] = nums[i - k]
}
for i := 0; i < k; i++ {
nums[i] = temp[i]
}
}
方法二:使用额外n 个数组
2.2解题思路
第一步:建立一个创建了一个和原数组 nums
长度相同的新切片num,用于临时存储旋转后的元素。第二部:对于原数组中索引为 i
的元素,向右旋转 k
个位置后的新索引为 (i + k) % len(nums);第三步:copy(nums, newNums)
将新数组的内容复制到原数组 nums
中,实现 “原地修改” 的效果(虽然内部用了新数组,但最终修改了原数组的内容)。
代码展示:
func rotate(nums []int, k int) {
n := len(nums)
temp := make([]int, n)
for i := 0;i < n; i++ {
temp[(i+k)%n] = nums[i]
}
copy(nums,temp)
}
方法三:三次反转法
2.3解题思路
写一个翻转reverse函数,先整体旋转一次,再将前k个元素翻转一次,最后将后len(nums)个元素翻转一次
代码展示:
func rotate(nums []int, k int) {
n := len(nums)
k = k%n
if n == 0 || k == 0 {
return
}
reverse(nums,0,n-1)
reverse(nums,0,k-1)
reverse(nums,k,n-1)
}
func reverse(nums []int, start,end int) {
for start < end {
nums[start], nums[end] = nums [end], nums[start]
start++
end--
}
}