189. Rotate Array

Given an array, rotate the array to the right by k steps, where k is non-negative.

Follow up:

• Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

My Answer 1: Time Limit Exceeded (34 / 35 test cases passed.)

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 길이가 1 이거나 k 가 len(nums) 의 배수면 nums 그대로
        if len(nums) != 1 or k%len(nums) != 0:
            length = k%len(nums)
            for i in range(length):
                #rotate
                start = nums[i]
                for j in range(len(nums)):
                    temp = nums[j]
                    nums[j] = start
                    start = temp
                nums[0] = start

맨 첨엔 i+k 인덱스를 사용하려 했는데
[1,2] k=3 이런 경우는 에바인거 같아서.. 1개씩 rotate 해야겠다고 생각
그래서 k%len(nums) 만큼 돌리도록 했다

k%len(nums) 번 돌리면서 한칸씩 이동하면 되니까 맨 처음&마지막 값만 신경써주면 돼서
start 를 잡고 rotate 후에 nums[0] = start 를 해줬는데... 타임리밋이다

보니까 솔루션에도 비슷한 방식이 있던데 그거도 타임리밋임;

Using Extra Array

Solution 1: Runtime: 60 ms - 78.58% / Memory Usage: 15.5 MB - 62.36%

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

리스트 하나 더 만들어서 쓰는건데 O(n) 이다

Using Cyclic Replacements

Solution 2: Runtime: 60 ms - 78.58% / Memory Usage: 15.7 MB - 34.84%

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
        
        start = count = 0
        while count < n:
            current, prev = start, nums[start]
            while True:
                next_idx = (current + k) % n
                nums[next_idx], prev = prev, nums[next_idx]
                current = next_idx
                count += 1
                
                if start == current:
                    break
            start += 1

O(1) 이다.
이걸 외워야할 거 같다~~!!

근데 아직 이해안됨

Using Reverse

Solution 3:Runtime: 60 ms - 78.58% / Memory Usage: 15.5 MB - 86.08%

class Solution:
    def reverse(self, nums: list, start: int, end: int) -> None:
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start, end = start + 1, end - 1
                
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k %= n

        self.reverse(nums, 0, n - 1)
        self.reverse(nums, 0, k - 1)
        self.reverse(nums, k, n - 1)

이건 리버스를 이용한 천재같은 방식
이거도 O(1) 이다.

전체 리버스 후 k 를 기준으로 다시 앞부분 리버스하고 뒷부분 리버스하는식