Leetcode - Find All Numbers Disappeared in an Array(488)


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)

這個解法可以不用到額外的空間。

Array 

其他相關

comments powered by Disqus