Leetcode Note: Go - Find All Numbers Disappeared in an Array

Find All Numbers Disappeared in an Array - LeetCode
https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/

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

所感

• int 配列の nums を受け取り、スキップされている数値を推測して int 配列で return する

回答

golang solution beats 99% runtime - LeetCode Discuss
https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/discuss/790951/golang-solution-beats-99-runtime

func findDisappearedNumbers(nums []int) []int {
	length := len(nums)
	if length == 0 {
		return nil
	}

	res := make([]int, length)
	for _, v := range nums {
		res[v-1] = v
	}

	j := 0
	for i := 0; i < length; i++ {
		if res[i] == 0 {
			res[j] = i + 1
			j++
		}
	}

	return res[:j]
}

• 一度目の for ループで res に数列を準備
  • 昇順にソートされており nums に含まれていない数値の箇所は value が 0 となる
  • [4,3,2,7,8,2,3,1] という input なら [1 2 3 4 0 0 7 8] という res が出来上がる
    • 同じ数値が複数個あっても冪等で素晴らしい実装だ・・・
• 二度目の for ループで res を return するための整形
  • value が 0 の項目を算出して、それらを配列の先頭に移動
  • [1 2 3 4 0 0 7 8] なら [5 6 3 4 0 0 7 8] という res に整形される
• 整形した res の先頭を return して終了
  • return res[:j]

配列を return する要件の場合、なんとなく配列を新規作成するアプローチを前提にしてしまっていたが、配列を使いまわして先頭や最後尾部分だけを return するような実装も有りだし、ソッチのほうがメモリ効率も良くて学びになった