5通りの方法で189. Rotate Arrayを解く

長さnの配列をk個右に回転させる問題。

There are at least three different ways to solve this problem.と書いてあったので、色々試してみた。

Just a moment...

全探索

1個ずらす作業をk回繰り返す。

時間計算量はO(NxK)かかるが、inplaceで作業できるので空間計算量が0。

ただし、提出しても時間切れ。

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        k %= len(nums)
        
        for i in range(k):
            prev = nums[-1]
            for j in range(len(nums)):
                prev, nums[j] = nums[j], prev

pop/insert

末尾を先頭に持ってきた後に末尾を削除する。

popメソッドはデフォルトで末尾を削除する。

ただし、insertメソットはO(N)が要求されるため遅い。

TimeComplexity - Python Wiki

O(N)のinsertをK回繰り返すため時間計算量はO(K)。

inplaceで実行出来るので空間計算量はO(1)。

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        for i in range(k):
            nums.insert(0, nums[-1])
            nums.pop()

外部配列を使う

値を保存するための長さNの配列を別に用意する。

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

循環

K個先の値と入れ替え、そのまたK個先の値と入れ替え、・・・を繰り返していく。

スタート地点に帰ってきたら同じループに入ってしまうので、breakしてスタート地点を1つずらし、同じことを繰り返す。

入れ替えた回数countを保存しておき、全部でN個の要素を入れ替えたら終了するため時間計算量はO(N)。

空間計算量は数個の変数を確保するだけなのでO(1)。

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        k %= len(nums)
        n = len(nums)
        
        start_idx = 0
        count = 0
        
        while count < n:
            current_idx, prev_value = start_idx, nums[start_idx]
            while True:
                next_idx = (current_idx + k) % n
                nums[next_idx], prev_value = prev_value, nums[next_idx]
                current_idx = next_idx
                count += 1
                
                if start_idx == current_idx:
                    break
            
            start_idx += 1

反転

K個回転させるということは、全体を反転させた後、前方K個と残りのN-K個をそれぞれ反転させることに等しい。

O(N)の反転を3返すため、時間計算量は定数倍を取り除いてO(N)。

inplaceで実行可能なので外部メモリは必要なく、空間計算量はO(1)。

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