448. Find All Numbers Disappeared in an Array #

Problem #

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

Problem Summary #

Given an integer array where the range is 1 ≤ a[i] ≤ n (n = array size), some elements in the array appear twice, while others appear only once. Find all numbers in the range [1, n] that do not appear in the array. Could you complete this task without using extra space and with a time complexity of O(n)? You may assume that the returned array does not count as extra space.

Solution Approach #

• Find the numbers in the range [1,n] that do not appear in the array. The requirement is to use no extra space and have a time complexity of O(n).
• Since extra space cannot be used, we can only find a way to modify the original array, and this modification must be reversible. The time complexity also only allows us to use one level of loop. As long as we can mark the numbers that have appeared in one traversal, this problem can be solved as required. The author’s marking method here is to mark the element at the index |nums[i]|-1 as negative. That is, nums[| nums[i] |- 1] * -1. Note that nums[i] needs to take its absolute value, because it may have been set to negative by a previous number and needs to be restored. Finally, traverse the array again. If the current array element nums[i] is negative, it means that the number i+1 exists in the array. Output the result to the final array.

Code #

package leetcode

func findDisappearedNumbers(nums []int) []int {
	res := []int{}
	for _, v := range nums {
		if v < 0 {
			v = -v
		}
		if nums[v-1] > 0 {
			nums[v-1] = -nums[v-1]
		}
	}
	for i, v := range nums {
		if v > 0 {
			res = append(res, i+1)
		}
	}
	return res
}