leetcode 189. 轮转数组

问题描述

给定一个数组，将数组中的元素向右移动 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]

解题思路

一种直观的方法是反复移动数组的最后一个元素到第一个位置，重复 k 次。但这种方法的时间复杂度是 O(k*n)，会超时。

更好的方法是使用反转。首先将整个数组反转，然后将前 k 个元素反转，再将剩余元素反转，即可得到所需结果。

func rotate(nums []int, k int) {
    k %= len(nums)
    reverse(nums)
    reverse(nums[:k])
    reverse(nums[k:])
}

func reverse(nums []int) {
    left, right := 0, len(nums)-1
    for left < right {
        nums[left], nums[right] = nums[right], nums[left]
        left++
        right--
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。反转数组的时间复杂度是 O(n)，反转 k 个元素和反转剩余元素的时间复杂度均为 O(k/2)。
• 空间复杂度：O(1)，只需要常数级别的额外空间来存储变量。