Find All Duplicates in an Array

发表于 | 分类于

Find All Duplicates in an Array

题目描述：

给定一个数组要求找到数组中出现超过两次的数字。

例子：

具体描述见LeetCode442

解题思路：

本题有两种解题方式，一个是利用哈希表记录下已经出现的数字，而后如果在后序的遍历中又出现则将其保存到结果中；另外一种解法是，例如我们将2保存到数组中的第1个位置上，不断的判断位置上数组和index的关系，在将数字放在对应位置上后，剩下的出现多次的数肯定不在对应的位置上，将其保存到结果中即可。

代码如下：

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
27
28
29
30
31
32
33
34
35
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        map<int, int> hash;
        vector<int> res;
        for (int i = 0; i < nums.size(); i++){
            if (hash.find(nums[i]) == hash.end()){
                hash.insert({nums[i], 1});
            }else{
                res.push_back(nums[i]);
            }
        }
        return res;
    }
};
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        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 (int i = 0; i < nums.size(); i++){
            if (nums[i] - 1 != i){
                res.push_back(nums[i]);
            }
        }
        return res;
    }
};