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]   

解析：這道題簡單地考慮應該會用兩個for循環(huán)，外面的for循環(huán)從1到n，內(nèi)層循環(huán)將外面的數(shù)字與向量里面的元素以此比較，若沒有出現(xiàn)，則將外面的數(shù)字添加到結果向量中去。但是注意到題目的要求是O(n)runtime,所以這種簡單的方法需要的時間復雜度是O（n^2）。既然要縮減時間，那我們就考慮犧牲空間了。可以再多建一個向量，起到像圖的遍歷里面visit數(shù)組一樣的功能。然后將原向量里面的元素映射到新向量的地址，這樣就起到了記住向量元素的作用。

將向量b初始化為大小與原向量一樣，元素全為0。然后再將原向量里面的元素對應的地址設為1，再通過一個for循環(huán)就可以找出那些原向量里面沒有的元素了。

源代碼如下：

class Solution {public:    vector<int> findDisappearedNumbers(vector<int>& nums) {       int len=nums.size();        vector<int> b;        for(int i=0;i<len;i++)        b.push_back(0);        for(int i=0;i<len;i++)        {            int m=nums[i]-1;           b[m]=1;        }        vector<int> res;        for(int i=0;i<len;i++)        {if(b[i]==0)        res.push_back(i+1);        }        return res;            }};