2022/04/04

Leetcode Note: Go - Remove Duplicates From Sorted Array

Remove Duplicates from Sorted Array - LeetCode
https://leetcode.com/problems/remove-duplicates-from-sorted-array/

  • Go 言語で取り組んだメモ

所感

  • 渡された配列をループして、登場した数値をフラグ管理しつつ、初登場の値である場合だけをカウントしていけば良さそう

実装準備

func removeDuplicates(nums []int) int {
    return 0
}

func main() {
    // input := []int{1,1,2} // 2
    input := []int{0,0,1,1,1,2,2,3,3,4} // 5
    fmt.Println(input)
    
    output := removeDuplicates(input)
    fmt.Println(output)
}

v1 実装

func removeDuplicates(nums []int) int {
    count := 0
    m := map[int]bool{}

    for i := 0; i < len(nums); i++ {
        if _, ok := m[nums[i]]; ok == false {
            count++
            m[nums[i]] = true
        }
    }
    return count
}

func main() {
    // input := []int{1,1,2} // 2
    input := []int{0,0,1,1,1,2,2,3,3,4} // 5
    fmt.Println(input)
    
    output := removeDuplicates(input)
    fmt.Println(output)
}
  • これでユニークな数値をカウントすることは出来るようになった
  • が、問題を読み違えてた・・・
  • 重複を排除した数値を return する必要がある
    • [1, 1, 2] なら [1, 1]
    • [0, 0, 1, 1, 1, 2, 2, 3, 3, 4] なら [0, 1, 2, 3, 4]
  • しかし removeDuplicates の戻り値は int が指定されている・・・
    • どう return すれば良いんだろう・・・？

回答

Simple O(n) solution with explanation in Go - LeetCode Discuss
https://leetcode.com/problems/remove-duplicates-from-sorted-array/discuss/942382/Simple-O(n)-solution-with-explanation-in-Go

  • 2つ のポインタを使う
    • fast => 1
    • slow => 0
  • fast が配列の最後に到達していない間に index fast と slow の要素が同じか確認する
    • 同じ場合は fast を 1桁 動かす
    • 同じではない場合は 重複していない要素を slow の後ろにコピーする

  • fast が配列の最後に到達すると、すべて一意の要素が slow 配列 に格納される

    func removeDuplicates(nums []int) int {
	if len(nums) <= 1 {
		return 1
	}

	slow := 0
	fast := 1
	n := len(nums)

	for fast < n {
		if nums[fast] == nums[slow] {
			fast++
		} else {
			slow++
			nums[slow] = nums[fast]
		}
	}

	return slow + 1
}

  • そもそも問題文の Custom Judge に、どういう方法で回答を判定するかのロジックが記載されてた・・・

  • 1 以上の長さで、ソート済みの数値配列が渡されるので、配列要素の前後を比較して重複を判定し、ユニークな要素数を return すれば良い

  • 英語でも問題文はちゃんと読みましょう・・・

See Also