Epoch

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 extra space.

Example:

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

Output:
[5,6]

題意

給你n個數字，找出1~n中哪些數字沒出現過。

想法1

先配置一塊記憶體，存放這些數字是否出現過，出現過的紀錄為1

再配置一塊記憶體，紀錄剛剛未出現過的數字，並return

一開始卡在設定回傳大小

到底是returnSzie = n 還是 *returnSize = n

*，這周聽了Jserv的教誨，別再念star，而是該念value of, dereference

這樣完成了要做的事情，但是卻配置額外的記憶體，題意希望不配置額外記憶體，所以要再想想

想法2

參考http://blog.csdn.net/yutianzuijin/article/details/53861485的解法三

對input數字，將出現過的數字，作為index，並將那個index的數字乘上-1，最後正數的index即為沒出現過的數字

nums[abs(nums[i]-1)] = -abs(nums[abs(nums[i])-1])

這個想法就不用額外的記憶體紀錄哪些數字是否出現過

是個較好的做法