442. Find All Duplicates in an Array

https://leetcode.com/problems/find-all-duplicates-in-an-array/

Find All Duplicates in an Array - LeetCode

난이도 : medium

문제

주어진 배열에서 중복되는 모든 원소를 반환하라

 

문제의 제약사항에 최대 n의 개수는 10^5 개가 들어올 수 있으며 O(n) 수행시간으로 문제를 풀어야 한다. 단순히 반복문을 두번 사용하여 bruth-force 로 이문제는 풀리지만 제약사항에 의해서 TLE 가 발생 할 것이다.

 

소스코드

정렬을 이용하여 O(n*log n) 풀이를 해보았다.

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        
        sort(nums.begin(), nums.end());
        
        int prev = nums[0];
        
        vector<int> sol;
        for(int i = 1; i<nums.size(); i++) {
            if (prev == nums[i]) {
                sol.push_back(prev);
            }
            prev = nums[i];
        }
        
        return sol;
    }
};

 

O(n) 의 수행시간으로 처리 하려면 어떻게 해야 할까? 일단 다른 사람들에 풀이를 확인 해보자.

1. Bruteforce Apprch
Idea - Do Check Double Time For Each element

-> bruthforce 접근 방법은 역시나 TLE 가 발생한다.

Time Complexcity - O(N*N) <=Give You TLE
Space Complexcity - O(1)

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        if(nums.empty())return {};
        vector<int>ans;
        for(int i=0;i<nums.size();i++){
            for(int j=i+1;j<nums.size();j++){
                if(nums[i]!=nums[j])continue;
                else{
                    ans.push_back(nums[i]);
                    break;
                }
            }
        }
        return ans;
    }
};

 

2.Using Sort Solution
Idea - Do sort The array First Then Track Adjcent Element Is Same Or Not [Can be Done By XOR or Have an count Element]

정렬을 사용하고 XOR 연산을 이용하는 방법이다. 중복된 원소가 1 ^ 1 = 0 이기 때문에 해당 풀이가 유효하긴하다. 하지만 중복된원소가 2개 이상일때는 해당 풀이로는 문제를 해결 할 수 없다.

Time Complexcity - O(N*Log N)
Space Complexcity - O(1)

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        if(nums.empty())return {};
        vector<int>ans;
        sort(begin(nums),end(nums));
        int s = nums[0];
        for(int i=1;i<nums.size();i++){
            if(!(s^nums[i])){
                ans.push_back(nums[i]),i+=1;
                if(i<nums.size())s=nums[i];
                else break;
            }
                else s = nums[i];
        }
        return ans;
    }
};

 

3. Using Unordered map

Idea - Take An unordered_map To store frequency Of each Element And Return those Having Frequency 2

크 생각해보니 unordered map 을 사용하면 O(n) 으로 풀이가 가능하다. 삽입, 검색의 비용을 생각해보니 그렇다.

Time Complexcity - O(N)
Space Complexcity - O(N)

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        if(nums.empty())return {};
        vector<int>ans;
        unordered_map<int,int>mp;
        for(int no:nums)mp[no]++;
        for(auto it:mp)if(it.second==2)ans.push_back(it.first);
        return ans;
    }
};