[Heap][Medium] 347. Top K Frequent Elements

https://leetcode.com/problems/top-k-frequent-elements/description

 

Q. 주어진 숫자배열 nums에서 k번째까지 많이 나오는 수의 목록를 찾아 반환하라. 

 

Solution

 먼저 출현 빈도를 알아야 하니, frequency buff를 만든다. 

 다음으로, 이 출현 빈도만큼, map 이나 heap에 넣어 정렬되도록 한다. 

 그리고 k 만큼 해당하는 수를 찾아 리스트에 넣어 반환한다.

 

논리대로 코드를 만든다 .

 

vector<int> topKFrequent(vector<int>& nums, int k) 
{
    unordered_map<int, int> mapBuff;
    for(int k = 0; k < nums.size(); ++k)
    {
        mapBuff[ nums[k] ]++;
    }

    map<int, vector<int>> mapOrder;
    unordered_map<int, int>::iterator it = mapBuff.begin();
    for(; it != mapBuff.end(); ++it)
    {
        if(mapOrder.find(it->second) == mapOrder.end())
        {
            vector<int> vTemp{ it->first };
            mapOrder[it->second] = vTemp;
        }
        else 
        {
            mapOrder[it->second].push_back(it->first);
        }
    }

    vector<int> vRet;
    int cnt = 0;
    for(map<int, vector<int>>::reverse_iterator it2 = mapOrder.rbegin(); it2 != mapOrder.rend(); ++it2)
    {
        for(int z = 0; z < it2->second.size(); ++z)
        {
            vRet.push_back((it2->second)[z]);
            ++cnt;
            if(cnt >= k)    
            {
                it2 = mapOrder.rend();
                --it2;
                break;
            }
        }
    }
    return vRet;
}

 

 

ㅎㅎ 

힙을 쓰면 조금 더 빠르지 않을까 싶다.