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 <= 105
  • k is 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.

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 topk


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.

class Solution:
    def topKFrequent(self, nums, k: int):
        return list(zip(*collections.Counter(nums).most_common(k)))[0]
LeetCode 솔루션 357 / 15 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


알림 0