旋转数组

About 4 min

一道看起来很简单但是又有一定技巧的题(或许是我太菜)

原题如下

2020-02-16-19-34-34

我的思路

分析以及注意事项

因为数组旋转, 每个位置上的数据必然发生变化. 因此算法最优时间必然是O(N).
因此无论如何都要将数组所有元素遍历一遍, 因为每次变化, 只是数据替换, 因此我们知道空间最优必然是O(1).
而且题目要求空间复杂度为O(1). 因此想创建一个新数组往里塞数的想法已经被扼杀了.

这就很明显了, 我们只需要在外层对数组进行遍历, 或者计数, 当循环数组长度次数时, 算法结束.
内部需要一个变量temp用于存放当前替换的值nums[next]
next的计算方式必然是(next + k) % size, k为步长, size为数组大小. 取余是为了高位替换低位, 你必须在数组长度内进行操作.

对于以某个步长, 进行数组循环, 无非有两种情况:

发生局部循环, 数组无法全部遍历
数组能够全部遍历

可以参考下图, 分别以2, 3为步长进行1~8的循环遍历:
2020-02-16-19-48-02

当步长可整除时, 会发生局部循环, 这个很好理解.
当步长不可整除时, 无法在跨度为数组长度时回到起始位置. 因此无法闭环. 而下一次回到起始点, 也就是闭环只能是数组长度的步进长度倍.

额, 其实上面和我们算法关系不大, 只是提醒你担心局部循环的问题. 这也是我第一次写犯的错误.

如果达到局部循环, 那么next必然会回到起始遍历位置. 因此我们可以增加pre记录起始位置, 并在局部循环达成后, 让pre自增1, 开始下一个局部循环.

为什么这样做能在O(n)实现所有元素的替换呢?
因为, 关键原因在于每次循环都会发生元素替换. 而不产生漏换的原因在于, 我们考虑了局部循环的情况. 不能整除的必然只有一个闭环.

程序

package main

import "fmt"

func rotate(nums []int, k int) {
   size := len(nums)
   if size <= 1 || k < 1 || k==size{
      return
   }
   pre, next, temp := 0, 0, nums[0]
   for i:=0; i<size; i++ {
      next = (next + k) % size
      fmt.Printf("交换 %d, %d\n", temp, nums[next])
      nums[next], temp = temp, nums[next]
      for _, v := range nums {
         fmt.Printf("%d,", v)
      }
      fmt.Printf("\t %d\n", temp)
      if next == pre {
         fmt.Println("====重新设置", pre)
         pre++
         temp = nums[pre]
         next = pre
      }
   }

   for _, v := range nums {
      fmt.Print(v)
   }
}

func main() {
   nums := []int{1, 2, 3, 4, 5, 6}
   rotate(nums, 4)

}

结果

2020-02-16-20-46-14

leetcode结果:
2020-02-16-20-48-22

最优解

我们再谈一谈最优解

代码如下:

func rotate(nums []int, k int)  {
    if len(nums)==0 ||k==0||k%len(nums)==0{
        return
    }
    k=k%len(nums)
    reverseSlice(nums,0,len(nums)-1)
    reverseSlice(nums,0,k-1)
    reverseSlice(nums,k,len(nums)-1)
}

func reverseSlice(nums []int,i,j int){
    for ;i<j; {
        nums[i],nums[j]=nums[j],nums[i]
        i++
        j--
    }
}