（leetcode 189）旋转数组（4种思路）

原题如下：
参考官方题解链接，代码及本文理解为笔者手写。

方案1、n个数每个都后移1位，后移k次。

时间复杂度O(n*k)，不太推荐。

方案2、使用额外n个空间，存储，按照next=（now+k）%len（nums），将now位置的值直接写到新数组的对应的位置，这样没有覆盖值得问题，但是不符合题目要求。

空间复杂度O（n），不太推荐。

方案3、每位跳k，直到所有位都跳k

过程如下：
从初始值开始，将0写到0+k位置上，临时原保存0+k位置的值；
临时保存的0+k原值写到0+2k的位置上，临时保存0+2k的值；
…
记录移动值的个数，当等于len（nums）时，终止循环。

这个思路存在一点缺陷，就是当走了一圈回到原地，
例如[5,6,7,8],k=2中，
第一次改变值后[5,6,5,8],tmp=7;当前位置为0，next位置为2；
第二次改变值后[7,6,5,8],tmp=5;当前位置为2，next位置为0；
第三次改变值后[5,6,5,8],tmp=7;当前位置为0，next位置为2；
第四次改变值后[7,6,5,8],tmp=5;当前位置为2，next位置为0；
这样，即便走够了len(nums)次循环，也没有走到下标为1和3的位置，这是因为又回到了原点，重复走了0，2位置。

因此，作为循环的补充，在每次更改值之前先判断是不是位于原起点start，如果不是，则继续；如果是，则start+=1，now+=1，tmp=lst[now]。
也就是说，如果起点相同，我们将循环整体后移一位，再次起点相同，我们再整体移动一位，直到更改了len（nums）个元素。

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        l=len(nums)
        if l<2:
            return
        k=k%l
        
        count=0
        start=0
        index=0
        a=nums[index]
        while count<l:
        	#如果新一轮回到了起点，整体后移
            if index==start:
                start=(start+1)%l
                index=(index+1)%l
                a=nums[index]
            nxt=(index+k)%l
            #b暂存nxt的值
            b=nums[nxt]
            nums[nxt]=a
            #将b赋值给a，a是下一轮需要替换进去的元素
            a=b
            index=nxt
            count+=1

方案4、旋转数组

分三步：

对于数组[1,2,3,4,5,6,7],k=2
（1）整体反转，变[7,6,5,4,3,2,1]
（2）前k个反转[6,7,5,4,3,2,1]
（3）后n-k个反转，[6,7,1,2,3,4,5]

之所以这样想，笔者的想法是旋转是两个值之间的交换，不存在值覆盖的问题。
另外，可以这样想，
（1）将一个数组分成两部分，前n-k位、后k位。
[1,2,3,4,5,6,7],分为[1,2,3,4,5]、[6,7]两部分
（2）这两部分内部一直是有序的，只需要两者相互换位置。
即最终应为：[6,7]、[1,2,3,4,5]
（3）要换位置，整体逆序后两部分都会在应该的位置上。只是因为整体逆序后内部顺序反了。
此时为[7,6]、[5,4,3,2,1]
（4）作为对（3）的修正，分别将两部分内部顺序反转即可。

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if len(nums)<2:
            return
        k=k%len(nums)
        def reverse(lst,left,right):
            while left<right:
                lst[left],lst[right]=lst[right],lst[left]
                left+=1
                right-=1
        reverse(nums,0,len(nums)-1)
        reverse(nums,0,k-1)
        reverse(nums,k,len(nums)-1)

相比较来说，方案三较快一点，但是比较复杂，面试的时候可能会写不出来，方案4要直观的多，也没慢多少。