LeetCode Find All Duplicates in an Array Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements that appear twice in this array. Could you do it without extra space and in O(n) runtime? Example:

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

---

长度为n的数组中存储了1~n的若干个数，有的出现了两次，有的只出现了一次，所以还会有一些没有出现。现在要找出所有出现两次的数字。因为不能使用额外的空间，时间复杂度也只能O(n)，所以方法和LeetCode Find All Numbers Disappeared in an Array几乎一样。 第一种方法是取相反数，如果发现nums[idx]已经是负数了，说明nums[i]在之前出现过了。完整代码如下： [cpp] class Solution { public: vector<int> findDuplicates(vector<int>& nums) { vector<int> ans; for (int i = 0; i < nums.size(); ++i) { int idx = abs(nums[i]) – 1; if (nums[idx] > 0) { nums[idx] = -nums[idx]; } else { ans.push_back(abs(nums[i])); } } return ans; } }; [/cpp] 本代码提交AC，用时188MS。 第二种方法是把每个数放到它正确的位置，第二遍扫描的时候，如果发现数字和下标对不上，则存储的数字就是出现两次的数字，对应的下标+1就是没出现过的数字（LeetCode Find All Numbers Disappeared in an Array解法2）。完整代码如下： [cpp] class Solution { public: vector<int> findDuplicates(vector<int>& nums) { vector<int> ans; for (int i = 0; i < nums.size(); ++i) { if (nums[nums[i] – 1] != nums[i]) { swap(nums[nums[i] – 1], nums[i]); –i; } } for (int i = 0; i < nums.size(); ++i) { if (nums[i] != i + 1) { ans.push_back(nums[i]); } } return ans; } }; [/cpp] 本代码提交AC，用时129MS。]]>