80. Remove Duplicates from Sorted Array II

問題概要

• 入力値は integerの配列 nums
• nums は昇順にソート済み
• nums を重複する要素が最大2回出現するように、重複要素を削除する
• nums のソート順は維持する（昇順のまま）
• 重複除去の結果は、nums の先頭部分に配置する
  • 重複を削除した後に k 個要素がある場合、nums の最初の k 要素を最終結果とする
  • k以降にどんな要素が残っていようと関係ない

例

Input: nums = [1,1,1,2,2,3]
Output: k = 5, nums = [1,1,2,2,3, x] xは何でも良い

問題URL：https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/description/

解法1

真っ先に思いついたのはハッシュテーブルを使ってカウントする方法。

func removeDuplicates(nums []int) int {
    counter := map[int]int{}
    k := 0
    for _, v := range nums {
        counter[v]++
        if counter[v] <= 2 {
            nums[k] = v
            k++
        }
    }

    return k
}

解法2

解法1だと「nums は昇順にソート済み」の条件を活用しきれていない。昇順にソート済みなら、前後の要素を比較するだけで済むはず。

そこで、ハッシュテーブルを使わない方法を考えてみた。

1. 重複は最大2回許されるため、先頭の2要素は確定
2. 3個目の要素から重複チェックをしていく
3. 「昇順ソート済み」かつ「重複は2回まで許される」という条件より、2個前の要素と比較すれば「除去すべきか」を判断できる
4. e.g. [0, 1, 1, 1, 2] の nums[3] の1を除去するかどうかは、nums[1] と同値かを見れば良い
5. 除去対象外なら先頭から順に値を入れていく

func removeDuplicates(nums []int) int {
    if len(nums) < 3 { // 要素2個以下なら除去する要素はない
        return len(nums)
    }

    // 要素が3個以上の場合、ここにくる
    // 先頭2個は除去対象にはならないので、2個からスタート
    k := 2
    for i := 2; i < len(nums); i++ {
        if nums[i] != nums[k-2] {
            nums[k] = nums[i]
            k++
        }
    }

    return k
}

感想

解法1はすぐに思いついたが、2は15分かかった。
ただ、Submissionsを見ずに思いついたので少し成長を感じれた。

次は、5分で解法2を思いつけるようになりたい。