[LeetCode]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]

题意：

一个大小为n的数组，数组里的数字大小范围为1到n，有些数字出现两次，有些数字出现一次，将出现两次的数字找出来。该题和第448题很类似。思路也基本一致。448题解题思路

题目关键是数字大小范围为1到n，不能使用额外的空间。

不能使用额外的空间，就要在原数组上进行处理，也可以采用数据取负数的方法。就是根据数组中数字和索引下标进行分析。

跟448题一样，遍历一遍数组。数值-1当作下标值，并将访问该下标值的数，如果为正数，则将正数变为负数（负数就表示该数已经访问过，已经出现了一次），如果为负数，则表示该数已经被遍历，出现过了一次，所以将该下标值+1存在数组中，此数就是出现两次的数，遍历一遍结束后，所有的出现两次的数都被保存在了数组中。动手画一遍数字改变的过程～

vector<int> findDuplicates(vector<int>& nums) 
    {
        vector<int> res;//存放结果的数组
        for(int i=0; i<nums.size(); i++)
        {
            int index = abs(nums[i])-1;//数减1作为下标值
            if(nums[index]<0)
                res.push_back(index+1);//如果为负数，则表示索引值出现过
            else
                nums[index] = -nums[index];
        }
        return res;
    }

该题还有一种解法，该解法使用了桶排序的思想，桶排序最后得到的数组为数字和数组下标相等。具体思路在代码注释中有所解释～不如上一种方法。

vector<int> findDuplicates(vector<int>& nums) 
    {
        vector<int> res;//存放结果的数组
        int i =0;
        int num = nums.size();
        while(i<num)
        {
            int index = nums[i]-1;//取索引值
            if(nums[i]!=nums[index])
                //如果num[i]与nums[index]不相等，则交换数字，这样保证索引为index的数的大小为index+1，就等于num[index]
                //这样遍历一遍以后，出现过的数都可以在数组中对号入座，两次出现的数，其中一个数在不正确的位置上
                swap(nums[i],nums[index]);
            else
                i++;
        }
        for(int i=0;i<num;i++)
        {
            if(nums[i]!=i+1)
                //不相等则说明该数出现了两次，因为肯定另一个数已经在正确的位置上
                res.push_back(nums[i]);
        }
        return res;
    }

leetCode的第41题也采用了这样的思想，大家可以尝试一下。