leetcodeOJ 442. 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]

把元素a[i]放在nums[a[i]-1]上，根据题意每个元素1<=a[i]<=n，因此不会超出数组的范围，然后再统计a[i]不在nums[a[i]-1]上的。

代码如下：

class Solution { public: vector<int> findDuplicates(vector<int>& nums) { vector<int> ans; for(int i = 0; i < nums.size(); ){ if(nums[i] == nums[nums[i]-1]) i++; else swap(nums[i], nums[nums[i]-1]); } for(int i = 0; i < nums.size(); i++){ if(nums[i] != i+1) ans.push_back(nums[i]); } return ans; } };