RSSフィードを購読
Python Coding Challenge (two-pointer sliding window technique)
(Python コーディングチャレンジ [ツーポインター / スライドウィンドウ テクニック編])
(Python コーディングチャレンジ [ツーポインター / スライドウィンドウ テクニック編])
今回は list (配列) のテクニックを磨くための練習問題です。いわゆる two-pointer technique / sliding window technique と呼ばれているものになります。
問題：
次のような処理を行なう関数を記述してください。
0 を含む int 値を要素とする list が与えられます。すべての 0 の要素を list の最後尾に移動し、0 ではない要素をその分 list の前に詰めていきます。この時、0 ではない要素の順番は元の list 内の順番と同じでなければいけません。
例えば次のようになります:
与えられる list: [0, 1, 0, 3, 12]
処理後の list: [1, 3, 12, 0, 0]
処理後の list: [1, 3, 12, 0, 0]
ただし以下の条件を守ってください:
与えられる list 以外の list を作成してはいけません。与えられた list だけを操作します。
Python で提供されているシーケンス操作関数 pop() や insert() 等を利用してはいけません。インデックス番号による操作のみが許可されます。
関数定義は以下のような形です (同じである必要はありません):
def move_zeros_to_last_two_pointer_technique(nums_list: list[int]) -> None:
...
if __name__ == '__main__':
a = [0, 1, 0, 3, 12]
print(move_zeros_to_last_two_pointer_technique(a)) # [1, 3, 12, 0, 0]
...
if __name__ == '__main__':
a = [0, 1, 0, 3, 12]
print(move_zeros_to_last_two_pointer_technique(a)) # [1, 3, 12, 0, 0]
考え方と解答例:
この問題を読んでまず「パッ」と頭に浮かぶ方法は、list を先頭からスキャンしていき 0 が見つかった時点でそれより後ろの要素を１つずつ前へ詰め list の最後を 0 で埋める、というものではないでしょうか？この時「0 をどこまで埋めたのか」を押さえておくためのポインタを利用する、といったバリエーションも考えられます。実装してみるとこんな感じでしょうか:
ネストループ を利用した実装例:
def move_zeros_to_last_simple_solution(a: list[int]) -> None:
index = 0
insert_index = len(a)
while index < insert_index:
if a[index] == 0:
for i in range(index + 1, insert_index):
a[i - 1] = a[i]
insert_index -= 1
a[insert_index] = 0
else:
index += 1
index = 0
insert_index = len(a)
while index < insert_index:
if a[index] == 0:
for i in range(index + 1, insert_index):
a[i - 1] = a[i]
insert_index -= 1
a[insert_index] = 0
else:
index += 1
この方法では 0 を見つけるたびに list の残り部分を操作するためのもう１つのループが必要となりループのネストが出現します。よってこのアルゴリズムの最悪実行時間は O(n²) となりあまり効率がいいとは言えません。
そこで、今回の主眼である two-pointer technique (ツーポインターテクニック: ２つのポインタを利用する方法) を利用します。この方法の基本的な考え方は次のようなものです:
２つのポインタを利用します。１つは list 内の各要素を最初から最後まで１つずつ順番にスキャンしていくためのポインタ (element_index) で、もう１つは「0 ではない要素」を埋める場所を指すポインタ (insert_index) です。
つまり、nums_list という list が与えられた場合の手順を言葉で表すと次のようになります:
element_index と insert_index を 0 に初期化します。
element_index を nums_list の最後まで１つずつ移動していきます。
nums_list[element_index] が 0 でなければ nums_list[insert_index] にその値を入力し insert_index を +1 します。
element_index が nums_list の最後まで到達したら、nums_list[insert_index] から最後の要素までを 0 で置き換えます。
図で表すと次のようになります:
Two-pointer technique
- Shyamkant Limaye (2021). Python Quick Interview Guide. BPB Publications -
Two-pointer technique を利用した実装例:
def move_zeros_to_last_two_pointer_technique(nums_list: list[int]) -> None:
insert_index = 0
for element_index in range(len(nums_list)):
if nums_list[element_index]:
nums_list[insert_index] = nums_list[element_index]
insert_index += 1
for i in range(insert_index, len(nums_list)):
nums_list[i] = 0
insert_index = 0
for element_index in range(len(nums_list)):
if nums_list[element_index]:
nums_list[insert_index] = nums_list[element_index]
insert_index += 1
for i in range(insert_index, len(nums_list)):
nums_list[i] = 0
Two-pointer technique を利用することでネストループが消え、list のスキャンも「最初から最後まで」の１回きりになっています。これにより最悪実行時間も O(n) となり格段に効率が良くなります。
今回の問題では「0 が見つかったら」という文章がポイントの１つですね。この文章を「正直」に受け取ると最初のような実装になるのではないでしょうか？
発想を転換して「0 以外が見つかったら」と解釈することで、２つのポインタを同じ方向に動かしながら処理をする今回の実装に結び付きます。