https://leetcode-cn.com/problems/rotate-array/
原题
给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。
示例 1:
输入: [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:
输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
说明:
尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
要求使用空间复杂度为 O(1) 的 原地 算法。
题目分析
本题有多种解法,要求使用原地算法。原地算法通俗的理解就是算法输出结果覆盖算法的输入,基本上不需要额外辅助的数据结构,省内存。
解法一
当 k = n 时,有 n 次向右移动,我们可以用数组的交换来模拟向右移动的步骤。
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
const rotate = (nums, k) => {
const length = nums.length
for (let i = 0; i < k; i++) {
let last = nums[nums.length - 1]
for(let j = 0; j < length; j++) {
const current = nums[j]
nums[j] = last
last = current
}
}
}
在每一次移动中,当第 i 个元素移动时,当前元素应该换为第 i - 1 个元素,所以需要在外层记住第 i - 1 个元素的值。一共进行 k 次移动。
该方法时间复杂度为 o(n^2)
,空间复杂度为 o(1)
。
解法二
仔细看,数组的旋转过程类似于队列的数据结构,向右移动一位相当于队列推出一位,然后在队列前添加一位。
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
const rotate = (nums, k) => {
const length = nums.length
const time = k % length
for (let i = 0; i < time; i++) {
const flag = nums.pop()
nums.unshift(flag)
}
}
解法三
利用数组翻转 reverse,先将所有元素翻转,然后将 0 ~ k % n - 1 位翻转,再将 k % n ~ n - 1 位翻转。
const reverse = (nums, start, end) => {
for (let i = start; i <= end; i++) {
const flag = nums[i]
nums[i] = nums[end]
nums[end] = flag
start += 1
end -= 1
}
}
const rotate = (nums, k) => {
const length = nums.length
reverse(nums, 0, length - 1)
k = k % length
reverse(nums, 0, k - 1)
reverse(nums, k, length - 1)
}
时间复杂度为 o(n)
,空间复杂度为 o(1)
。