LeetCode #80 ソートされた配列の重複要素を削除
問題文
昇順の整数配列が与えられ、
配列の中に、同じ要素が2回以上表示されたら、その残りの要素を削除します。
要素の相対的な順序を保つ必要があります。
最後に、重複要素を削除した配列の長さを返します。
DoublePointerで解く
まず、チェック用のファストポインタと止め用のスローポインタを用意します。
この問題では、要素が2回以上表示されたらアウトのため、ファストポインタとスローポインタはインデックス2の所に初期化して、そこから、どんどん比べていきます。
ファストポインタの数字と、スローポインタより二つ前と一つ前の数字を比べて、
2回以上表示されていないなら、ファストポインタの数字はこの配列の中に2回以上重複していないと証明できます。
逆に言うと、スローポインタより二つ前と一つ前の数字と比べて、何れも同じなら、ファストポインタの数字は3回以上表した数字なので、重複していない数字が表すまでに、止め用のスローポインタはそのまま移動させません。
ファストポインタが配列の最後まで移動したら、配列を既にチェック済みとのことで、スローポインタのインデックス番号をプラス1にしたら、重複していない配列の長さとなります。
JavaScript Code
var removeDuplicates = function(nums) {
if(nums.length<=2) return nums.length
let fast=2;
let slow=2;
while(fast<nums.length){
if(nums[fast]!==nums[slow-1] || nums[fast]!==nums[slow-2]){
nums[slow]=nums[fast]
slow++
fast++
}else if(nums[fast]==nums[slow-1] && nums[fast]==nums[slow-2]){
fast++
}
}
return slow
};