🐷

【いつ使うねん】アルゴリズムの2ポインタ法を理解した

に公開
Python
アルゴリズム
2ポインタ法
tech

2ポインタ法

指定数字を排除

two_pointer_remove_element.py
# ex)
# nums = [3,2,2,3]
# val = 3
# output = [2,2,_,_]
# k = 2
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if not nums:
            return 0
        k = 0 # 書き込みポインタを定義
        for i in range(len(nums)): # 読み込みポインタを定義
            if nums[i] != val:
                nums[k] = nums[i]
                k += 1 # 削った数をカウント
        return k

上記が2ポインタ法という、in-placeに配列を操作する方法です。
上記だとvalで指定された文字を排除する、という役割を担っています。

index0から順にみていき、指定数字valと異なっていたら書き込みポインタにおいてその数値を書き込むという感じ。
問題を解いていて、慣れていないと「valと一緒の時に○○しよう」という思考になりがちだなと思いました。

重複を排除

下記のように「配列の重複をなくす」という処理にも使用できます。

two_pointer_remove_dupulicates.py
# numsは昇順にソートされている前提
# ex)
# nums = [1,2,2,4,4,6]
# output = [1,2,4,6,_,_]
# k = 4
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        k = 1 # 1つ目は必ず残すから書き込みポインタは1から
        for i in range(1, len(nums)): # 読み込みポインタも1から
            if nums[i] != nums[i-1]: # ここでindex0と1を比較している
                nums[k] = nums[i]
                k += 1 # 残った数をカウント
        return k

上記の計算量はいずれもO(n)ですかね。
リストを2つのポインタが動くものの、iがnだけ動いたらkのポインタも止まるので2重にカウントする必要がなさそうです。

最初考えていた解法

  • 配列の後ろから走査
  • 最後尾が指定数字か否かで処理が変わる
    • 指定数字なら一つ前を見る。指定数字以外が来るまで繰り返す
    • 指定数字で無いならフラグ立てて次の数字見る
    • その後一つ前を見て指定数字なら一つ後と入れ替え、違うならまた一つ前を見る、ということを繰り返せば行けるのでは

上記はよく考えると指定数字以外が連続した後に指定数字が来た際の入れ替えが面倒になることに気づきました。
バブルソートと同じでO(n^2)となり筋が悪いですね。

感想

いつ使うねん。

と思いましたが、調べてみるとモデル作成時の前処理などで使うことも多そう。
データクレンジングなどで使用するのがメインのようです。

トップレベルエンジニアは呼吸のように使っているテクニックなのでしょうか。
使うかどうかはおいておいて、アルゴリズムはやっていて面白いので、引き続きちょこちょこ進めていきます。

Discussion