美文网首页
数组三次反转

数组三次反转

作者: raito4 | 来源:发表于2021-06-07 18:43 被阅读0次

    三次反转
    对于[1,2,3,4,5,6,7][1,2,3,4,5,6,7],
    根据k=k%nk=k%n,将数组分为两段:

    第一段,对应数组下标范围[0,n-k-1][0,n−k−1]段,即[1,2,3,4][1,2,3,4]
    第二段,对应数组下标范围[n-k,n-1][n−k,n−1],即[5,6,7][5,6,7]
    分为三步:

    1. 反转第一段,[4,3,2,1,5,6,7]
    2. 反转第二段,[4,3,2,1,7,6,5]
    3. 反转整体,[5,6,7,1,2,3,4]

    code:

    class Solution:
        def rotate(self, nums: List[int], k: int) -> None:
            """
            Do not return anything, modify nums in-place instead.
            """
            n = len(nums)
            k = k%n
            def swap(l,r):
                while l < r:
                    nums[l],nums[r] = nums[r],nums[l]
                    l += 1
                    r -= 1
            swap(0,n-k-1)
            swap(n-k,n-1)
            swap(0,n-1)
    
    
    # insert
    class Solution:
        def rotate(self, nums: List[int], k: int) -> None:
            n = len(nums)
            k %= n
            for _ in range(k):
                nums.insert(0, nums.pop())
    
    

    相关文章

      网友评论

          本文标题:数组三次反转

          本文链接:https://www.haomeiwen.com/subject/zznfeltx.html