📚 LeetCode - 26. Remove Duplicates from Sorted Array ソート済み配列の重複を削除する方法

📌 問題の概要

整数の配列 nums が 昇順（小さい順）にソート されています。
この配列から 重複を削除 し、各要素が 一度だけ登場するように 変更してください。

✅ 条件

• 配列を「その場で」（in-place）変更すること。
• 元の並び順を維持 すること。
• ユニークな要素の数 k を返す こと。
• k 以降の配列の要素は何が入っていてもOK！

🌟 例

🎯 例1

入力:

nums = [1,1,2]

出力:

2, nums = [1,2,_]

説明:

• 1 が2回あるので1つ削除。
• nums = [1, 2, _] となり、k = 2 を返す。

🎯 例2

入力:

nums = [0,0,1,1,1,2,2,3,3,4]

出力:

5, nums = [0,1,2,3,4,_,_,_,_,_]

説明:

• 0, 1, 2, 3, 4 の ユニークな要素を前に詰める。
• k = 5 を返す。

🛠 解き方（Two Indexes Approach）

🤔 考え方

1. 配列はソート済み！ ➝ つまり、重複する要素は 連続して並ぶ。
2. 2つのインデックスを使う：
   • insertIndex 👉 書き込む場所
   • i 👉 現在の位置（読み取り用）
3. i が進みながら、前の値と違う要素があれば insertIndex に格納！

🔥 アルゴリズム（流れ）

1. insertIndex = 1（書き込む位置）を設定。
2. i = 1 からスタートしてループ。
3. nums[i] != nums[i-1] なら、nums[insertIndex] = nums[i] とする。
4. insertIndex を1つ進める。
5. 最後に insertIndex を返す（ユニークな要素の数）。

💻 コード（Python）

from typing import List

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        size = len(nums)
        insertIndex = 1  # 先頭は常にユニーク

        for i in range(1, size):  # 1からスタート
            if nums[i - 1] != nums[i]:  # 直前の値と異なる場合
                nums[insertIndex] = nums[i]  # 重複しない要素を前に詰める
                insertIndex += 1  # 書き込み位置を1つ進める

        return insertIndex  # k（ユニークな要素の個数）を返す

🔄 処理の流れ

🌟 例

nums = [0,0,1,1,1,2,2,3,3,4]

i	insertIndex	nums
1	1	[0,0,1,1,1,2,2,3,3,4]
2	2	[0,1,1,1,1,2,2,3,3,4]
5	3	[0,1,2,1,1,2,2,3,3,4]
7	4	[0,1,2,3,1,2,2,3,3,4]
9	5	[0,1,2,3,4,2,2,3,3,4]

最後に k = 5 を返す！ 🎉

📈 時間・空間計算量

• 時間計算量: O(n)（ループ1回）
• 空間計算量: O(1)（追加の配列を使わない）

🎯 まとめ

✅ 2つのポインタ（insertIndex, i）を使う
✅ ソート済みであることを利用し、前の値と比較
✅ 追加の配列を使わずに O(n) の時間で処理！

これで nums の重複を削除できる！🚀🔥