More than 1 year has passed since last update.

【LeetCode】#80 Remove Duplicates from Sorted Array II

Last updated at 2022-02-06Posted at 2022-02-06

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

};