LeetCode 솔루션 분류
347. Top K Frequent Elements
본문
[Leetcode 시즌 3] 2022년 4월 8일 문제입니다
[Medium] 347. Top K Frequent Elements
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]
Example 2:
Input: nums = [1], k = 1 Output: [1]
Constraints:
1 <= nums.length <= 105kis in the range[1, the number of unique elements in the array].- It is guaranteed that the answer is unique.
Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
관련자료
-
링크
댓글 3
mingki님의 댓글
- 익명
- 작성일
C++
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
map<int, int> m;
for (auto n : nums) {
m[n]++;
}
vector<pair<int, int>> sorted(m.begin(), m.end());
sort(sorted.begin(), sorted.end(), [](const pair<int, int> &lhs, const pair<int, int> &rhs) {
return lhs.second > rhs.second;
});
vector<int> res;
for (int i = 0; i < k; ++i) {
res.push_back(sorted[i].first);
}
return res;
}
};bobkim님의 댓글
- 익명
- 작성일
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
std::map<int,int> m;
std::vector<int> ans;
int max=0;
//Count frequency
for(int i=0;i<nums.size();i++){
m[nums[i]]++;
};
//find kth frequent elements
std::map<int,int>::iterator itrTmp;
for(int i=0;i<k;i++){
for(std::map<int,int>::iterator itr=m.begin();itr!=m.end();itr++){
if((itr->second) >= max){
itrTmp=itr;
max=itr->second;
};
};
max=0;
ans.push_back(itrTmp->first);
m.erase(itrTmp);
};
return ans;
}
};Jack님의 댓글
- 익명
- 작성일
https://github.com/JackKimUSA/leetcode-python-solutions
Python3
Submissions:
- Runtime: 104 ms, faster than 40.69% of Python3 online submissions for Top K Frequent Elements.
- Memory Usage: 18.7 MB, less than 43.85% of Python3 online submissions for Top K Frequent Elements.
Submissions:
- Runtime: 96 ms, faster than 82.16% of Python3 online submissions for Top K Frequent Elements.
- Memory Usage: 18.5 MB, less than 54.35% of Python3 online submissions for Top K Frequent Elements.
Python3
Submissions:
- Runtime: 104 ms, faster than 40.69% of Python3 online submissions for Top K Frequent Elements.
- Memory Usage: 18.7 MB, less than 43.85% of Python3 online submissions for Top K Frequent Elements.
class Solution_1:
def topKFrequent(self, nums, k: int):
freqs=collections.Counter(nums)
freqs_heap=list()
for f in freqs:
heapq.heappush(freqs_heap, (-freqs[f], f))
topk = []
for _ in range(k):
topk.append(heapq.heappop(freqs_heap)[1])
return topkSubmissions:
- Runtime: 96 ms, faster than 82.16% of Python3 online submissions for Top K Frequent Elements.
- Memory Usage: 18.5 MB, less than 54.35% of Python3 online submissions for Top K Frequent Elements.
class Solution:
def topKFrequent(self, nums, k: int):
return list(zip(*collections.Counter(nums).most_common(k)))[0]
