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?

思路

注意题目要求不用多余空间，并且时间复杂度为O(n).
由于本题特殊性在于这个数组只有出现1次和2次的数据，所以遍历数组，把其对应index上的数置为相反数。如果遍历到一个数已经是负数，那么这个数就是重复的。
（真聪明啊）

思路2：一直交换到nums[i]和nums[nums[i]-1]相等指针指向下一个。
也就是把数字放在他们本来应该在的位子，然后遍历看谁占的位子不对谁就是重复的。
但是复杂度是O(n)吗？交换好像也用到了extra space.

经过思考，我认为这个算法是O(n)的。算法主要是两层，第一层是遍历整个数组，也就是指针i，另一层是每次i涉及到的交换，每次交换确定一个数的位置，所以总的交换次数是O(n)。不存在每个指针都需要交换n次的。所以不是O(n^2)。

代码

vector<int> res;
for(int i=0;i<nums.size();i++)
{
    int index=abs(nums[i])-1;
    if (nums[index]<0)
    {
        res.push_back(abs(nums[i]));
    }
    nums[index]=abs(nums[index])*-1;

}

return res;

改的简洁一点：

vector<int> findDuplicates(vector<int>& nums) {

vector<int> res;
for(int i=0;i<nums.size();i++)
{
    int index=abs(nums[i])-1;
    if (nums[index]<0)
    {
        res.push_back(index+1);
    }
    nums[index]=-nums[index];

}

return res;
    
}

思路2代码：

vector<int> res;
int i = 0;
while (i < nums.size()) {
    if (nums[i] != nums[nums[i]-1]) swap(nums[i], nums[nums[i]-1]);
    else i++;
}
for (i = 0; i < nums.size(); i++) {
    if (nums[i] != i + 1) res.push_back(nums[i]);
}
return res;