算法练习——189.轮转数组

发布于:2025-09-02 ⋅ 阅读:(21) ⋅ 点赞:(0)

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--
    }
}


网站公告

今日签到

点亮在社区的每一天
去签到