力扣地址
给定一个整数数组 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

进阶:

  • 尽可能想出更多的解决方案,至少有 三种 不同的方法可以解决这个问题。
  • 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?

解法一:

数学方法

func rotate(nums []int, k int) {
    n := len(nums)
    //只需要计算最终翻转的位置
    k = k % n
    if k == 0 {
        return
    }
    left := 0
    i := 0
    for i < n {
        //由0开始向前替换
        pre, cur := nums[left], left
        //替换到重复位置开始下一个数
        for ok := true; ok; ok = cur != left {
            //持续按着k间隔向后替换
            right := (cur + k) % n
            nums[right], pre, cur = pre, nums[right], right
            //计算替换数量,到总量退出
            i++
        }
        left++
    }
}

解法二:

取巧法,翻转数组:

如 n = 9; k=3:

  • -123456789->
  • <-987654321-
  • <-987-<-654321-
  • -789-><-654321-
  • -789->-123456->

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

func reverse(a []int) {
    for i, n := 0, len(a); i < n/2; i++ {
        a[i], a[n-1-i] = a[n-1-i], a[i]
    }
}
Last modification:June 21, 2024
如果觉得我的文章对你有用,请收藏本站