Leetcode 189. rotation array

Power button | 189. Rotation array

Title screenshot

Method 1 ： Three reverses

Whenever k be equal to n Double speed , Complete a whole cycle , Equivalent to no change .

utilize k=k%n, Remove the invalid changes .

Divide the whole array into two parts , The final result is obtained after three reversals .

for example ：nums=[1, 2, 3, 4, 5, 6, 7]

k = 3

Is divided into [1, 2, 3, 4] and [5, 6, 7] Two paragraphs .

Reverse the first paragraph for the first time , have to [4, 3, 2, 1, 5, 6, 7].

Reverse the second paragraph for the second time , have to [4, 3, 2, 1, 7, 6, 5].

Reverse all for the third time , have to [5, 6, 7, 1, 2, 3, 4].

Complexity

Time complexity

Spatial complexity

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n
        def swap(l, r):
            while(l<r):
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
                r -= 1
        swap(0, n-1-k)
        swap(n-k, n-1)
        swap(0, n-1)

Complete test code

from typing import List

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


class main:
    a = Solution()
    nums = [-5, -4, -3, -2, -1]
    k = 3
    a.rotate(nums,k)
    print(nums)


if __name__ == '__main__':
    main()

  With the help of python The slice of completes the inversion

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n
        nums[:] = nums[::-1]
        nums[:k] = nums[:k][::-1]
        nums[k:] = nums[k:][::-1]

 

Method 2 ： Direct use python section

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n
        nums[:] = nums[n-k:] + nums[:n-k]

Method 3 ： Directly create a new array

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        ans=[0]*n
        for i in range(0, n):
            ans[(i+k)%n] = nums[i]
        for i in range(0, n):
            nums[i] = ans[i]

Method four ： Circular substitution

Location  0  The element will be placed in  (0+k)mod n It's about , Repeated movement in this way will form a moving closed loop .

Of course , This does not completely traverse every element , So the circular movement is completed , After returning to the original position , Just move down one element , Then start such a circular movement .

When can I traverse all the elements ？

Element number n And moving step k The greatest common divisor of is the number of circular movements .

Total number of moving steps = Number of circular movements * Number of moving steps in the ring

So set the inner and outer loops .

The number of outer cycles is the greatest common divisor , Inner circulation moves instead , When the replacement returns to the starting position, exit the inner loop .

import math

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n
        count = math.gcd(k, n)
        for start in range(0, count):
            current = start
            prev = nums[start]
            while True:
                next = (current + k) % n
                nums[next], prev = prev, nums[next]
                current = next
                if next == start:
                    break

Expand ： Custom maximum common divisor

division

    def my_gcd(x, y):
        while x%y:
            x, y = y, x%y
        return y

iteration

    def my_gcd(x, y):
        return x if y==0 else self.my_gcd(x, x%y)