[数据结构与算法]LeetCode 442. 数组中重复的数据

具体思路：

自己想了个原地交换思路，每次搜索，交换元素，如果发现应该存在的位置上有元素了，则说明是重复元素，空出来的位置变为-1，方便插入；

但是本题考查的是原地Hash思想，讲对应的i位置上+n，访问的时候取模，之后遍历即可；

具体代码：

交换版本：

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int>vec;
        for(int i=0;i<nums.size();i++){
            if(nums[i]!=i+1){
                //可以进行迭代;
                int next=nums[i]-1;
                int pre=nums[i];
                nums[i]=-1;
                while(nums[next]!=next+1&&nums[next]!=-1){
                    int temp=nums[next]-1;
                    nums[next]=pre;
                    pre=temp+1;
                    next=temp;
                }
                if(nums[next]==next+1){
                    vec.push_back(nums[next]);
                }else if(nums[next]==-1){
                    nums[next]=next+1;
                }
            }
        }
        return vec;
    }
};

原地取模hash版本：

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int>vec;
        int n=100100;
        for(int i=0;i<nums.size();i++){
            int index=nums[i]%n-1;
            nums[index]+=n;
        }
        for(int i=0;i<nums.size();i++)
            if(nums[i]>2*n)
                vec.push_back(i+1);
        return vec;
    }
};