[LeetCode] 448. Find All Numbers Disappeared in an Array

轉自LeetCode

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]

<Solution>

想法如下

• 因為 1 ≤ a[i] ≤ n，所以 0 ≤ index = a[i] - 1 < n。因此，可以先歷遍一次 array，把可以 access 到的位置，都變成負數，表示來過

• 再歷遍一次，只要該 index 所在的位置是正數，代表 index + 1 = missing number

code 如下

C++

如果今天題目放寬條件，可以允許有負數，那麼上面解法就無法使用

這時候可以改成用 swap 的方式來處理

假設 a[i] = k 且 a[k-1] != a[i]，則 swap(a[i], a[k-1]) 

之後只要檢查 a[i] != i+1 的，就是 missing number

Kotlin