Question
Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.
Example 1:
Input: nums = [4,3,2,7,8,2,3,1] Output: [5,6] Example 2:
Input: nums = [1,1] Output: [2]
Solution
1.
func findDisappearedNumbers_solution_one(nums []int) []int{
m := make(map[int]bool)
for _, num := range nums {
m[num] = true
}
fmt.Printf("map: %v\n", m)
var result []int
length := len(nums)
for i := 1; i <= length; i++{
_, ok := m[i]
if !ok {
result = append(result, i)
}
}
return result
}
解題思考： 第一種簡單粗暴，用一個 Set 去存所有的 value。 然後從 1 loop 到 n 。 沒有在 Set 裡的就是不見的。
2.
func findDisappearedNumbers_solution_two(nums []int) []int{
length := len(nums)
for i := 0; i < length; i++{
index := abs(nums[i])- 1
if nums[index] > 0 {
nums[index] = -nums[index]
}
}
j := 0
for i := 0; i < length; i++{
if nums[i] > 0 {
nums[j] = i+1
j++
}
}
return nums[:j]
}
func abs(a int)int{
if a < 0 {
return -a
}
return a
}
解題思路：
這個解法真的是滿神奇的，不看別人解，這種方式完全沒想過。
我們從 array 第一個開始取，拿到 value 之後，把該 value 當 index 去把這個 index 裡面的 value 改為負數(做記號)
把 array 遍歷完後。再遍歷一次，這時候還是正數的 index 就是消失的值。(這裡利用了題目的特性，因為題目說給你 n 長度的 array 裡面的值最大不會超過 n)
這個解法可以不用到額外的空間。