LeetCode 配列の基本的な質問

基本的な質問

リートコード 26

問題の簡単な説明:

ソートされた配列を指定した場合、各要素が 1 回だけ表示されるように、繰り返される要素を所定の位置で削除し、削除された配列の新しい長さを返す必要があります。

ここには大まかに 2 つの解決策があります。1 つ目はダブル ポインターです。

public int removeDuplicate(int[] nums){
    if(nums.length==0){
        return 0;
    }
    int j= 0;//遅いポインタ
    for(int i =1;i<nums.length;i++){//高速ポインタ
        if(nums[i]!=nums[j]){
            j++;
            nums[j]=nums[i];
        }
    }
    return j+1;
    
}

この質問で最も重要なことは、重複データをすべて削除する必要はなく、最初のいくつかを置き換えるだけであることを明確にすることです。 たとえば、{0,0,1,1,2,2} の場合、最終的には {0,1,2} ではなく {0,1,2,1,2,2} に変更するだけです。 この点を明確にしておけば、この質問ははるかにやりやすくなります。

ここで初心者が混乱しやすいのは、配列内の繰り返しデータがどのようにカバーされるかということです (具体例としては、テスト ケースの入力 {0, 0, 0, 1, 1, 2, 3})。 具体的な演算過程は、ファストポインタ i が 1 になるまで j は常に存在し、i が 3 に増加したときのみ、この時点で次の判定文が実行され、つまりまず j が 1 に増加します。次に、nums[j+1]、つまり nums[1] を num[i]、つまり nums[3] の数に変更します。 等々。

2 つ目の書き方は、LinkedHashSet の内容が繰り返されず、順序が保証されるという特性を利用する方法です。

public int removeDuplicate1(int[] nums){
        LinkedHashSet<Integer> set = new LinkedHashSet();//
        for(int n : nums){
            set.add(n);// for ループ で配列内の数値をセットに詰め込みます
        }

        int i =0;
        for(int j : set){
            nums[i++]=j;
        }//元の配列を上書きします
        return set.size();//必要な数値を返す
    }