🙆♀️
26. Remove Duplicates from Sorted Array
整数配列 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 (
・ループ後に $i + 1 を返却(インデックスなので+1)。
Discussion