[leetCode] Top Interview 150: Remove Duplicates from Sorted Array II

個人的にめっちゃ苦戦した。

リンク

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/?envType=study-plan-v2&envId=top-interview-150

概要

• 昇順にソートされた整数配列numsが与えられる
• これをin-placeな方法で2個以上の重複を取り除いた形にする

解法

前問と同じようにいけるかと思ったらハマった。
解法は以下の通り。

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length <= 2) {
            return nums.length;
        }

        int index = 2;
        for(int i=2; i<nums.length; i++) {
            if(nums[i] != nums[index-2]) {
                nums[index] = nums[i];
                index++;
            }
        }

        return index;
    }
}

前回はnums[i] != nums[i-1]のときに置き換えをしていたが、今回はnums[i] != nums[index-2]のときに置き換えている。

これは置き換える先を新しい空の配列だと仮定したときに、indexが指す場所はその配列の末尾であり、nums[i] == nums[index-2]のときに挿入を行ってしまうと、同じ数が3つ以上横に並んでしまうから。
何を言っているかわからないと思うが、私も最初はかなり混乱しました。混乱の原因がin-placeな実装にあり、「逆に新しい配列を用意する形で実装したらどうなるか」を考えたときにこの考え方に気付きました。

前回は見たまま考えればサクッと解けたばかりに、猫騙しを食らった気分です。