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;
}
결과.
'Leetcode > NeetCode' 카테고리의 다른 글
[ArraysHashing][Medium] 238. Product of Array Except Self (0) | 2024.07.08 |
---|---|
[ArraysString][Medium] 271. Encode and Decode String (0) | 2024.07.08 |
[ArraysHashing][Medium] 49. Group Anagrams (0) | 2024.07.07 |
[ArraysHashing][Easy] 1. Two Sum (0) | 2024.07.07 |
[ArraysHasing][Easy] 242. Valid Anagram (0) | 2024.07.07 |