dequeを使ったリストのローテション

問題

今日はPrint left rotation of array in O(n) time and O(1) spaceの問題に挑戦する。今までチャレンジしてきたローテション問題をdequeを使って解く方法でチャレンジする。

k = 3
Input: [1, 3, 5, 7, 9]
output: [7, 9, 1, 3, 5]

まずは基本的なローテションを実装してから、デックを使ったローテションの実装にチャレンジする。

実装1

from typing import List

def leftRotate(numbers: List[int], k: int):
    len_numbers = len(numbers)
    mod = k % len_numbers
    res =[]

    for i in range(len_numbers):
        res.append(numbers[(mod + i) % len_numbers])
    return res


if __name__ == '__main__':
    numbers = [1, 3, 5, 7, 9]
    print(leftRotate(numbers, k=3))

[7, 9, 1, 3, 5]

dequeについて

Pythonの標準ライブラリcollectionsモジュールのdeque型は、リストに比べて、先頭の要素に対する削除や追加、挿入が速い。一方で、両端以外の要素へのアクセスは遅いデメリットもある。

import collections

d = collections.deque()

for i in range(5):
    d.append(i)

print(d)
d.rotate(-3)
print(d)

for _ in range(5):
    print(d.pop(), end=' ')

deque([0, 1, 2, 3, 4])
deque([3, 4, 0, 1, 2])

rotate()メソッドでローテションさせることができるので、これを使って回転させたものを左から取り出す。

import collections

d = collections.deque()
for i in range(5):
    d.append(i)
    
d.rotate(-3)

for _ in range(5):
    print(d.popleft(), end=' ')

3 4 0 1 2 

実装2

ということでdequeについては少し理解ができたので、この問題にチャレンジする。方針としては、リストをdequeに変換し、dequeのメソッドでローテションさせて、リストに戻すという方法。

from collections import deque
from typing import List

def leftRotate(numbers: List[int], k: int):
    len_numbers = len(numbers)
    numbers = deque(numbers)

    numbers.rotate(-k)
    numbers = list(numbers)

    res = []

    for i in range(len_numbers):
        res.append(numbers[i])

    return res


if __name__ == '__main__':
    numbers = [1, 3, 5, 7, 9]
    print(leftRotate(numbers, k=3))

[7, 9, 1, 3, 5]