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]
题目大意:
找出数组中出现两次的元素。
把每个元素“归位”即可，注意是将每个元素归位，而不是把每个位置上移动来应该有的元素，因为每个元素一定有对应的位置，但是不是每个位置都能有正确的元素归位，因为存在重复的元素。因此，将每个元素都进行了归位操作以后，如果进行归位操作的时候，位置上的元素和本身一样，那就不移动了。那么最后遍历数组，如果数字和位置不对应，那么这个元素就出现了2次。把所有的元素存到数组中，返回即可。
题目代码:
class Solution {
public:vector<int> findDuplicates(vector<int>& nums) {vector<int> ans;int i = 0;while(i < nums.size()){if(nums[i] != nums[nums[i]-1])swap(nums[i], nums[nums[i]-1]);elsei++;}for(int i = 0; i < nums.size(); i++){if(nums[i] != i+1)ans.push_back(nums[i]);}return ans;}
};