leetcode 442. Find All Duplicates in an Array 重复元素查找+很棒O(n)做法-蒲公英云

leetcode 442. Find All Duplicates in an Array 重复元素查找+很棒O(n)做法

梦里梦外; 2022-06-04 08:25 302阅读 0赞

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]

题意很简单，直接使用set遍历查询即可

首先来看一种正负替换的方法，这类问题的核心是就是找nums[i]和nums[nums[i] - 1]的关系，我们的做法是，对于每个nums[i]，我们将其对应的nums[nums[i] - 1]取相反数，如果其已经是负数了，说明之前存在过，我们将其加入结果res中即可，参见代码如下

要和leetcode 448. Find All Numbers Disappeared in an Array 寻找缺失元素+很棒O(n)做法一起学习

代码如下：

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <string>
#include <climits>
#include <algorithm>
#include <sstream>
#include <functional>
#include <bitset>
#include <numeric>
#include <cmath>
#include <regex>
#include <iomanip>
#include <cstdlib>
#include <ctime>
using namespace std;
class Solution
{
public:
    vector<int> findDuplicates(vector<int>& a)
    {
        vector<int> res;
        for (int i = 0; i < a.size(); i++)
        {
            int idx = abs(a[i]) - 1;
            if (a[idx] < 0)
                res.push_back(idx + 1);
            a[idx] = -a[idx];
        }
        return res;
    }
    vector<int> findDuplicatesBySet(vector<int>& nums)
    {
        vector<int> res;
        set<int> ss;
        for (int a : nums)
        {
            if (ss.find(a) == ss.end())
                ss.insert(a);
            else
                res.push_back(a);
        }
        return res;
    }
};