LeetCode Find All Numbers Disappeared in an Array 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]

---

一个长度为n的数组，保存了1~n中的若干个数，有的出现了两次，有的出现了一次，有的数没有出现，现在要找出那些没有出现的数。要求线性时间复杂度和常数空间复杂度。 这一题有点意思，要求不使用额外的空间，那么唯一的办法就是借助原数组进行操作了。我们可以把数组中的数字都放到它们正确的位置上，然后扫描一遍数组，如果某个位置存储的数字和下标对不上，则这个位置存储的是出现两次的数字，同时说明下标对应那个数字没有出现在原数组中。 这种解法的代码如下： [cpp] class Solution { public: vector<int> findDisappearedNumbers(vector<int>& nums) { vector<int> ans; for (int i = 0; i < nums.size(); ++i) { if (nums[i] != nums[nums[i] – 1]) { swap(nums[i], nums[nums[i] – 1]); –i; } } for (int i = 0; i < nums.size(); ++i) { if (nums[i] – 1 != i) { ans.push_back(i + 1); } } return ans; } }; [/cpp] 本代码提交AC，用时159MS。 还有一种解法是，对于每一个数字nums[i]，如果它对应的nums[nums[i]-1]是正数，则把nums[nums[i]-1]赋值为自身的相反数；否则不变。最后重新扫描一遍数组，如果是负数，则说明对应数字存在，否则下标对应数字不存在。这个不难理解，比如题目中的例子，nums[0]=4，则把nums[nums[0]-1]赋值为-nums[nums[0]-1]=-7，这样第二遍扫描nums数组时，发现下标为3的数字是负数，则说明数字4存在于原始数组中。 这种解法的代码如下： [cpp] class Solution { public: vector<int> findDisappearedNumbers(vector<int>& nums) { vector<int> ans; for (int i = 0; i < nums.size(); ++i) { int idx = abs(nums[i]) – 1; nums[idx] = nums[idx]>0 ? (-nums[idx]) : nums[idx]; } for (int i = 0; i < nums.size(); ++i) { if (nums[i] > 0)ans.push_back(i + 1); } return ans; } }; [/cpp] 本代码提交AC，用时142MS。]]>