leetcode_find_all_duplicates_in_an_array

发表于

难度：Medium

使用最后的结果数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        int sz = nums.size();
        vector<int> ret(sz+1,0);
        for(int i = 0; i < nums.size(); i++)
        {
            ret[nums[i]]++;
        }
        for(int i = 0; i <= sz; i++)
        {
            if(ret[i] == 2)
                ret.push_back(i);
        }
        ret.erase(ret.begin(),ret.begin()+sz+1);
        return ret;
    }
};

142ms,93.06%

遍历数组，如果nums[i]与i+1相等，则continue；如果不相等，则tmp = nums[i]，tmp－1为nums[i]应该在的位置，如果nums[i]与nums[tmp-1]不相等，交换nums[i]与nums[tmp-1]的元素，此时不要记录重复元素，会有重复的情况。交换完元素之后，遍历数组求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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

192ms,28.85%

用额外空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int>temp(nums.size(),0);
        vector<int>ret;
        for(int i = 0;i < nums.size();i++)
        {
            int cur = nums[i];
            temp[cur-1]++;
        }
        for(int i = 0;i < nums.size(); i++)
        {
            if(temp[i] == 2)
                ret.push_back(i+1);
        }
        return ret;
    }
};

149ms，73.67％