[LeetCode] 645. Set Mismatch

https://leetcode.com/problems/set-mismatch/description/?envType=daily-question&envId=2024-01-22

LeetCode - The World's Leading Online Programming Learning Platform

LeetCode - Set Mismatch

문제 유형 : 해시

문제 난이도 : Easy

 

문제

You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.

You are given an integer array nums representing the data status of this set after the error.

Find the number that occurs twice and the number that is missing and return them in the form of an array.

 

당신은 정수 집합 s를 받는다. 1부터 n까지의 수가 담겨있다.

불행하게도, 에러 때문에 숫자 하나가 바뀌어서 다른 한 숫자가 대신 2개가 되었다.

당신은 에러가 발생한 정수 배열 nums를 받는다.

어느 숫자가 중복되는지와 어느 숫자가 없어졌는지를 찾아서 배열의 형태로 반환하시오.

 

풀이

map에 [숫자 - 개수] 형태로 저장한다.

nums를 순차적으로 순회하면서 개수를 1씩 늘려가며 저장한다.

그 뒤, map[i]의 숫자를 1씩 빼준다.(1 <= i <= n)

 

그러면 하나씩 있는 값들은 0을 나타내고, 두 개가 있는 숫자는 1, 사라진 숫자는 -1로 남는다.

1을 가진 값과 -1을 가진 값을 찾아서 반환하면 된다.

 

코드

C++

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        
        const int n = nums.size();
        unordered_map<int, int> mp;
        int missing, dup;

        for(const auto &num : nums) {
            mp[num]++;
        }

        for(int i = 1; i <= n; i++) {
            mp[i]--;
        }

        for(const auto &m : mp) {
            if(m.second == -1) {
                missing = m.first;
            } else if(m.second == 1) {
                dup = m.first;
            }
        }

        return {dup, missing};
    }
};