[692. Top K Frequent Words] #leetcode

692_1015.java

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        // hashmap stores counts of each words
        HashMap<String, Integer> map = new HashMap<>();
        for(String s : words){
            map.put(s, map.getOrDefault(s, 0) + 1);
        }
        // PQ to get top k elements
        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(
            (a, b) -> a.getValue() == b.getValue() ? b.getKey().compareTo(a.getKey()): a.getValue() - b.getValue()
        );
        
        for(Map.Entry<String, Integer> m : map.entrySet()){
            pq.offer(m);
            if(pq.size() > k){
                pq.poll();
            }
        }
        
        // return top k
        List<String> res = new LinkedList<>();
        while(!pq.isEmpty()) {
            res.add(0, pq.poll().getKey());
        }
        
        return res;
    }
}

692_1015.py

import collections

class Solution(object):
  # O(nlogn) O(n)
    def topKFrequent(self, words, k):
        """
        :type words: List[str]
        :type k: int
        :rtype: List[str]
        """
        counts = collections.Counter(words)   
        freqs = sorted((-count, word) for word, count in counts.items())
        return [f[1] for f in freqs][:k]


# O(nlogk) O(n), python 2
import collections
import heapq

class Element:
    def __init__(self, count, word):
        self.count = count
        self.word = word
        
    def __cmp__(self, other):
        if self.count == other.count:
            return -cmp(self.word, other.word)
        return cmp(self.count, other.count)

class Solution(object):
    def topKFrequent(self, words, k):
        """
        :type words: List[str]
        :type k: int
        :rtype: List[str]
        """
        counts = collections.Counter(words)   
        
        freqs = []
        heapq.heapify(freqs)
        for word, count in counts.items():
            heapq.heappush(freqs, (Element(count, word), word))
            if len(freqs) > k:
                heapq.heappop(freqs)
        
        res = []
        for _ in range(k):
            res.append(heapq.heappop(freqs)[1])
        return res[::-1]

# python 3
import collections
import heapq
import functools

@functools.total_ordering
class Element:
    def __init__(self, count, word):
        self.count = count
        self.word = word
        
    def __lt__(self, other):
        if self.count == other.count:
            return self.word > other.word
        return self.count < other.count
    
    def __eq__(self, other):
        return self.count == other.count and self.word == other.word

class Solution(object):
    def topKFrequent(self, words, k):
        """
        :type words: List[str]
        :type k: int
        :rtype: List[str]
        """
        counts = collections.Counter(words)   
        
        freqs = []
        heapq.heapify(freqs)
        for word, count in counts.items():
            heapq.heappush(freqs, (Element(count, word), word))
            if len(freqs) > k:
                heapq.heappop(freqs)
        
        res = []
        for _ in range(k):
            res.append(heapq.heappop(freqs)[1])
        return res[::-1]