Zenn
🙆‍♀️

26. Remove Duplicates from Sorted Array

2025/03/14に公開
整数配列 nums が非減少順にソートされている場合、重複をその場で削除し、各ユニークな要素が1回だけ現れるようにします。要素の相対的な順序は維持する必要があります。その後、nums 内のユニークな要素の数を返します。

実装条件
nums 内のユニークな要素の数を k と考え、以下の条件を満たす必要があります:

配列 nums を変更して、最初の k 個の要素がユニークな要素で、もとの順序を保持するようにします。
nums の残りの要素は重要ではありません。
k を返します。

以下のコードであなたの実装をテスト。

int[] nums = [...]; // 入力配列
int[] expectedNums = [...]; // 正しい長さの期待される結果

int k = removeDuplicates(nums); // 実装された関数の呼び出し

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}
全てのアサーションが成功すれば、解答は正しいと判断されます。

例 1
入力: nums = [1,1,2]
出力: 2, nums = [1,2,_]
説明:
関数は k = 2 を返すべきです。nums の最初の2つの要素はそれぞれ 1 と 2 でなければなりません。k 以降の要素は関係ありません(_ で示しています)。

例 2
入力: nums = [0,0,1,1,1,2,2,3,3,4]
出力: 5, nums = [0,1,2,3,4,_,_,_,_,_]
説明:
関数は k = 5 を返すべきです。nums の最初の5つの要素は、それぞれ 0, 1, 2, 3, 4 である必要があります。k 以降の要素は関係ありません。

このようにして、配列の重複をその場で削除し、ユニークな要素の数を返すアルゴリズムを実装する必要があります。
class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function removeDuplicates(&$nums) {

        
       $n = count($nums);

       if($n == 0) return 0;

       $i = 0;
       for($j = 0; $j < $n; $j++) {
            if($nums[$i] !== $nums[$j]) {
                $i++;
                $nums[$i] = $nums[$j];
            }
       }

       return $i + 1;
    }
}

・$i はユニーク要素のインデックスを管理。
・$j は配列を順に走査。
・if (nums[nums[i] != nums[nums[j]) でユニーク要素をチェック。
・ループ後に $i + 1 を返却(インデックスなので+1)。

Discussion

ログインするとコメントできます