【アルゴリズム】2ポインタだと気づいていたのにpopしてしまった話

目次

• 解いた問題
• 学び
• 最初に考えた解法
• 正解
• 感想

解いた問題

leetcode 283 Move Zeroes
ランダムに整数が入ったリスト型のnumsが与えられるから、その中から0を抜き出して、ほかの数字の順序を変えずに0を末尾に持ってきてねって問題。

リストはコピーを作るのではなくインプレース、すなわち1つのリスト内だけで動かしてねって問題。

学び

• 意外と直感的に解放を思いつくようになってきた
• コードに落とし込めるかは別

最初に考えた解法

なんとなく2ポインタ法で行けそうだなと感じた。

とはいえ具体的に考えてみたら、0があるインデックスを指定してpop、それを末尾に追加すれば行けそうだな、と思ってしまい、このやり方だと2ポインタ法使わないで行けそう。

とりあえずそのまま実装してみた。

first.py

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for i in range(0, len(nums)):
            if nums[i] == 0:
                x = nums.pop(i)
                nums.append(x)
            i += 1

失敗。
例を見ると[0,0,1]の順で入ってきたとき、1つ目の0を末尾に移した瞬間2個目の0がインデックス0に移動してうまくできていなさそう。

改修として0を何個移動させればいいかカウントし、その分appendすればいいのではと思った。
が、forで回すインデックスを末尾から使っていってpopすればインデックスずれが起きないのではと考えた。

second.py

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for i in range(len(nums)-1, -1, -1):
            if nums[i] == 0:
                x = nums.pop(i)
                nums.append(x)

これで正解。
問題は時間計算量。

forが1つなので$O(n)$かと思いきや2乗オーダー。
調べたところボトルネックはpopだった。

list[i]での要素指定自体は$O(1)$だが、list.pop(i)だと、要素を抜いた後それより後ろの要素を前詰めする処理が裏で走ってしまう。

そのためnオーダーとなりforの中にあるから2乗オーダーになる。

正解

最適解は下記。

answer.py

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        k = 0  # 次に非ゼロを書き込む位置：書き込みポインタ

        # 1) 非ゼロだけ前に詰める（相対順序を維持）
        for x in nums:　# 走査ポインタ
            if x != 0:
                nums[k] = x
                k += 1

        # 2) 残りを 0 で埋める
        for i in range(k, len(nums)):
            nums[i] = 0

2ポインタ法でできるそう。

ネックとなる前づめを先に完了させ、書き込みポインタkから0を長さ分埋めるという発想。

感想

最近2ポインタ法やってなかったこともありどう使うのかパットでなくなっていた。

なんとなく2ポインタ法を使うんだなと感づいていたのはよかったと思うべきか。

3月以降はアルゴリズムに加えてシステムデザインなどのキャッチアップがしたいと思っている次第。