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

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

 

숫자 배열이 주어질 때, k 번째로 많이 등장하는 원소까지 찾아라.

 

 

여러 가지 방법이 있을 수 있다. 

frequency buffer를 만들고 frequency 수로 정렬한다. 

map을 이용해서 정렬할 수도 있고, priority queue를 이용할 수도 있다. 

 

하지만, follow up에서 보다시피, O(nxlog(n)) 을 넘지 말라고 명시하고 있다.

따라서 조금 더 생각해 볼 여지가 있다. 

 

일단 sort 나 일반 map 은 정렬에 의존하므로, n x log(n) 이다. 이것은 기준에 부합하지 않는다. 

다음으로 priority queue를 보자. 

insert 시 O(n), pop 시에 heapify를 하면서 log(N)을 사용한다. 

따라서 정렬이 n x log(n)을 쓰는 반면, priority queue는 k 까지만 pop을 하므로 k x log(n)이므로 정렬보다는 빠르다. 

하지만 여전히 최적해 인지는 의문스럽다. 

 

다음으로 count sort를 확인하자. 

입력의 개수가 input array로 한정적이다. 

이 수대로 count 해서 각 count에 해당하는 index에 해당 num을 넣어준다. 

그리고 뒤에서 부터 k 까지 출력한다. O(n)으로 깔끔하다.
 

 

vector<int> ArraysHashing::topKFrequent(vector<int>& nums, int k)
{
    unordered_map<int, int> mFreq;
    for (auto q = 0; q < nums.size(); ++q)
    {
        mFreq[nums[q]]++;
    }

    // Count Sort.
    vector<vector<int>> vData;
    vData.resize(nums.size(), vector<int>{});
    for (auto iter = mFreq.begin(); iter != mFreq.end(); ++iter)
    {
        int idx = iter->second - 1;
        int num = iter->first;
        vData[idx].push_back(num);
    }

    vector<int> vRet;
    for (auto q = vData.size() - 1; q >= 0; --q)
    {
        for (auto j = 0; j < vData[q].size(); ++j)
        {
            vRet.push_back(vData[q][j]);
            if (vRet.size() >= k)
                return vRet;
        }
    }
    return vRet;
}

 

결과.