Leetcode 347. Top K Frequent Elements 692. Top K Frequent Words (python)

题目

解法1：排序 (NlogN)

class Solution(object):def topKFrequent(self, nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""count = collections.Counter(nums)tmp = list(set(nums))tmp.sort(key = lambda x:count[x],reverse = True)ans = []for i in range(k):ans.append(tmp[i])return ans;

解法2：heap (Nlogk)

class Solution(object):def topKFrequent(self, nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""count = collections.Counter(nums)heap = [(-v,key) for key,v in count.items()]heapq.heapify(heap)#print(heap)return [heapq.heappop(heap)[1] for _ in range(k)]

上面的heap是nlogn的，下面的heap解法是nlogk的
C++版本：注意一下heap的元素是pair的情况

class Solution {
    
public:vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int,int> count;for(auto num : nums){
    count[num] += 1;}priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>>> pq;for(auto pair : count){
    if(pq.size() < k){
    pq.push({
    pair.second,pair.first});}else{
    pq.push({
    pair.second,pair.first});pq.pop();}}vector<int> ans;while(!pq.empty()){
    ans.push_back(pq.top().second);pq.pop();}return ans;}
};

692. Top K Frequent Words

与上一题解法一模一样

解法1：排序

class Solution(object):def topKFrequent(self, words, k):""":type words: List[str]:type k: int:rtype: List[str]"""count = collections.Counter(words)candidates = count.keys()candidates.sort(key = lambda x:(-count[x],x))return candidates[:k]

解法2：heap

class Solution(object):def topKFrequent(self, words, k):count = collections.Counter(words)heap = [(-freq, word) for word, freq in count.items()]heapq.heapify(heap)return [heapq.heappop(heap)[1] for _ in xrange(k)]