給一串在區(qū)間1~n內(nèi)的數(shù)字array款熬，這些數(shù)字出現(xiàn)了0次，1次或2次岛心，找出出現(xiàn)了0次的那些數(shù)字题画。
O(n) Time O(n) Extra Space
用一個boolean [] map來記錄數(shù)字是否重復(fù)。
O(nlogn) Time O(1) Extra Space
sort()压储，然后在gap處把缺少的加到結(jié)果里鲜漩。
O(n) Time O(1) Extra Space
其實我一直以為每個數(shù)字出現(xiàn)兩次是突破口，但是這題的突破口是所有數(shù)字都是positive integer集惋，這樣你就可以把數(shù)字映射回它本身對應(yīng)的那個slot孕似，而且只要用正負號來做標記。注意不能漏了 if(nums[Math.abs(nums[i])-1]>0)這句否則出現(xiàn)兩次的數(shù)字對應(yīng)的slot的標記會被取消刮刑。
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> res = new ArrayList<>();
if(nums == null || nums.length == 0) return res;
for(int i = 0 ; i < nums.length ; i ++){
if(nums[Math.abs(nums[i])-1]>0)
nums[Math.abs(nums[i])-1] = -nums[Math.abs(nums[i])-1];
}
for(int i = 0 ; i < nums.length ; i ++){
if(nums[i]>0){
res.add(i+1);
}
}
return res;
}
