題目
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]
解題思路
題目大意如下：給定一個(gè)整型數(shù)組屯碴，數(shù)組元素的大小都在 1 到 n 之間，其中 n 為數(shù)組大小。元素可能出現(xiàn)一次或者兩次凡人，現(xiàn)在希望你能找出不屬于該數(shù)組蓝撇，但大小為[1,n]的元素，要求你的算法不需要使用額外的空間檐盟，并且時(shí)間復(fù)雜度為 O(n) 梯投。
題目的難點(diǎn)主要在于限定你設(shè)計(jì)的算法空間復(fù)雜度為 O(1)， 時(shí)間復(fù)雜度為 O(n)沟涨。一開(kāi)始自己直觀的想法就是先建立一個(gè)大小為 n 的布爾型數(shù)組恤批，初始化為false，然后遍歷一遍輸入數(shù)組裹赴，將出現(xiàn)的元素對(duì)應(yīng)的布爾值修改為true喜庞，最后只需再遍歷一遍布爾型數(shù)組，布爾值為false的數(shù)組下標(biāo)即為體重所求元素棋返。雖然該算法的時(shí)間復(fù)雜度為 O(n)延都， 但空間復(fù)雜度也為 O(n)， 顯然不滿足題意睛竣。
于是改變思路晰房，既然不能使用額外空間，而且不可能只遍歷一遍就可得到答案（至少需要兩次循環(huán)射沟，每次循環(huán)都能得到一定量的信息）殊者，那么原數(shù)組肯定需要發(fā)生一些改變來(lái)存儲(chǔ)第一次遍歷后得到的信息。沿著這個(gè)思路验夯，不難想出正確的算法猖吴，其中之一，如下所述：第一次循環(huán)將數(shù)組中元素作為下標(biāo)對(duì)應(yīng)的元素值變?yōu)樨?fù)數(shù)簿姨，第二次循環(huán)判斷元素值是否大于 0 距误， 大于 0 的話，說(shuō)明其下標(biāo)即為缺失值（在第一次循環(huán)中已經(jīng)將出現(xiàn)過(guò)元素作為下標(biāo)對(duì)應(yīng)的元素值變?yōu)樨?fù)數(shù)了扁位，好像有點(diǎn)繞口 ORZ 准潭，待會(huì)看看代碼就應(yīng)該很好理解了）。該算法空間復(fù)雜度為 O(1)域仇， 時(shí)間復(fù)雜度為 O(n)刑然， 滿足題意。
參考代碼
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
int len = nums.size();
for(int i=0; i<len; i++) {
int m = abs(nums[i])-1; // index start from 0
nums[m] = nums[m]>0 ? -nums[m] : nums[m];
}
vector<int> res;
for(int i = 0; i<len; i++) {
if(nums[i] > 0) res.push_back(i+1);
}
return res;
}
};
