📚 LeetCode - 27. Remove Element 配列の特定の要素をインプレースで削除する方法

🎯 問題の概要

与えられた整数配列 nums から、特定の整数 val をすべて削除してください。
このとき、配列の順序は変わってもOK ですが、配列自体を新しく作り直さずに（インプレースで）削除 する必要があります。
最後に、削除後の nums の要素数（val 以外の数） を返してください。

例えば、次のような配列があるとします：

nums = [1, 2, 3, 5, 4]   （削除する数字は 4）

この場合、4 を削除すると nums = [1, 2, 3, 5] になり、戻り値は 4 となります。

---

✅ 解答の条件

削除後の nums について、以下の条件を満たす必要があります：

1. nums の最初の k 個の要素は、val とは異なる値で構成される。
2. nums の後半部分（k 以降）は重要ではなく、どんな値が入っていてもOK（配列のサイズは考えなくてよい）。
3. k（削除後の nums の長さ）を返す。

---

💡 解決策 1：二つのポインタを使った方法（Two Pointers）

✨ アルゴリズム

1. i を 0 に設定（i は val 以外の要素を置いていくポジション）。
2. j を 0 から nums.length - 1 まで動かす。
3. nums[j] が val でない場合：
   • nums[i] = nums[j] にして、i を進める。
4. i が最終的に val 以外の要素数 k になるので、それを返す。

🎯 コード（Python）

from typing import List

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = 0
        for j in range(len(nums)):
            if nums[j] != val:
                nums[i] = nums[j]
                i += 1
        return i

---

💡 解決策 2：後ろから要素を入れ替えて削除する方法

✨ アルゴリズム

1. i を 0 に、n を配列の長さに設定。
2. i < n の間、繰り返し処理する：
   • nums[i] == val ならば：
     • 後ろの要素と入れ替える (nums[i] = nums[n-1])
     • 配列の長さを1つ減らす (n -= 1)
   • そうでなければ i を増やす。
3. n が新しい要素数（val 以外の数）なので、それを返す。

🎯 コード（Python）

from typing import List

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = 0
        n = len(nums)
        while i < n:
            if nums[i] == val:
                nums[i] = nums[n-1]
                n -= 1
            else:
                i += 1
        return n

🔥 どちらの方法を選ぶべき？ 🎯

方法	使うべき場合	メリット	デメリット
方法 1（Two Pointers）	val の数が多い	一定の順序を保ちつつ削除できる	val と同じ要素が少ないと無駄な代入が多くなる
方法 2（Swap & Shrink）	val の数が少ない	ループの数を減らせるため、コピー（代入）が減るので処理が速い	順序が崩れる

🎉 まとめ

✅「順序を崩してもいいなら、後ろから入れ替える方法 2（Swap & Shrink）が良い！」
✅「順序をなるべく保ちたいなら、前から詰める方法 1（Two Pointers）が便利！」

どちらの方法もメリットがあるので、問題に応じて使い分けよう 🚀🔥