検索ガイド -Search Guide-

単語と単語を空白で区切ることで AND 検索になります。
例: python デコレータ ('python' と 'デコレータ' 両方を含む記事を検索します)
単語の前に '-' を付けることで NOT 検索になります。
例: python -デコレータ ('python' は含むが 'デコレータ' は含まない記事を検索します)
" (ダブルクオート) で語句を囲むことで 完全一致検索になります。
例: "python data" 実装 ('python data' と '実装' 両方を含む記事を検索します。'python data 実装' の検索とは異なります。)
python_coding_challenge

Python coding challenge - リスト内の 0 を他の要素の順番は変えずに最後尾へ移動しよう! - two-pointer technique の利用 投稿一覧へ戻る

Published 2022年7月15日5:13 by mootaro23

SUPPORT UKRAINE

- Your indifference to the act of cruelty can thrive rogue nations like Russia -

Python Coding Challenge (two-pointer sliding window technique)
(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 以外の 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]
考え方と解答例:
この問題を読んでまず「パッ」と頭に浮かぶ方法は、list を先頭からスキャンしていき 0 が見つかった時点でそれより後ろの要素を1つずつ前へ詰め 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
この方法では 0 を見つけるたびに list の残り部分を操作するためのもう1つのループが必要となりループのネストが出現します。よってこのアルゴリズムの最悪実行時間は O(n²) となりあまり効率がいいとは言えません。
そこで、今回の主眼である two-pointer technique (ツーポインターテクニック: 2つのポインタを利用する方法) を利用します。この方法の基本的な考え方は次のようなものです:
2つのポインタを利用します。1つは list 内の各要素を最初から最後まで1つずつ順番にスキャンしていくためのポインタ (element_index) で、もう1つは「0 ではない要素」を埋める場所を指すポインタ (insert_index) です。
つまり、nums_list という list が与えられた場合の手順を言葉で表すと次のようになります:
element_index と insert_index を 0 に初期化します。
element_index を nums_list の最後まで1つずつ移動していきます。
nums_list[element_index] が 0 でなければ nums_list[insert_index] にその値を入力し insert_index を +1 します。
element_index が nums_list の最後まで到達したら、nums_list[insert_index] から最後の要素までを 0 で置き換えます。
図で表すと次のようになります:
python_coding_challenge_two_pointer_technique
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
Two-pointer technique を利用することでネストループが消え、list のスキャンも「最初から最後まで」の1回きりになっています。これにより最悪実行時間も O(n) となり格段に効率が良くなります。
今回の問題では「0 が見つかったら」という文章がポイントの1つですね。この文章を「正直」に受け取ると最初のような実装になるのではないでしょうか?
発想を転換して「0 以外が見つかったら」と解釈することで、2つのポインタを同じ方向に動かしながら処理をする今回の実装に結び付きます。