[LeetCode] 229. Majority Element II

https://leetcode.com/problems/majority-element-ii/description/

LeetCode - The World's Leading Online Programming Learning Platform

문제 유형 : 해시, 배열

문제 난이도 : Medium

 

문제

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

 

n의 크기를 가진 정수 배열 nums가 주어진다. n/3번 보다 많이 나온 배열의 요소들을 찾아 반환하시오.

 

풀이

key = 정수, value = 나온 횟수를 담는 해시 맵을 만들어서 개수를 저장해둔다.

만약 개수가 조건에 충족한다면, 따로 만든 배열에 정수를 담아주면 된다.

 

코드

C++

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);

        const int n = nums.size();
        const int minimum = n / 3;
        unordered_map<int, int> um;

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

        vector<int> result;
        for(const auto& num : um) {
            if(num.second > minimum) {
                result.push_back(num.first);
            }
        }
        return result;
    }
};