欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

(leetcode 189)旋转数组(4种思路)

程序员文章站 2024-03-08 19:30:42
...

原题如下:
(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=21)整体反转,变[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要直观的多,也没慢多少。
(leetcode 189)旋转数组(4种思路)