LeetCode 189 – Python 3 (Week 05 – 18)

Although I spend a lot of time in Cyclic Replacements method, I still couldn’t write the right program.

Solution 1

class Solution:
     def rotate(self, nums: List[int], k: int) -> None:
         """
         Do not return anything, modify nums in-place instead.
         """
         tmp = []
         tmp[:k] = nums[len(nums)-k:]
         tmp[k:] = nums[:len(nums)-k]
         for i in range(len(nums)):
             nums[i] = tmp[i]
 Cass Solution:
     def rotate(self, nums: List[int], k: int) -> None:
         """
         Do not return anything, modify nums in-place instead.
         """
         nums[:] = nums[len(nums)-k:] + nums[:len(nums)-k] 

Time complexity is O(n). Space complexity is O(n).

Solution 2

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

Time complexity is O(n). Space complexity is O(1).

Leave a comment

Design a site like this with WordPress.com
Get started