692. Top K Frequent Words - cocoder39/coco39_LC GitHub Wiki

class Pair:
    def __init__(self, frequence, word):
        self.frequence = frequence
        self.word = word
    
    def __lt__(self, pair):
        return self.frequence < pair.frequence or (self.frequence == pair.frequence and self.word > pair.word)

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        counter = Counter(words)
        min_heap = []
        for word, freq in counter.items():
            heapq.heappush(min_heap, Pair(freq, word))
            if len(min_heap) > k:
                heapq.heappop(min_heap)
        
        res = collections.deque()
        while min_heap:
            pair = heapq.heappop(min_heap)
            res.appendleft(pair.word)
        return res

public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> mp = new HashMap<>();
        for (String word : words) {
            mp.put(word, mp.getOrDefault(word, 0) + 1);
        }
        
        PriorityQueue<Map.Entry<String, Integer>> minHeap = 
            new PriorityQueue<>((entry1, entry2) -> (entry1.getValue() == entry2.getValue()
                                                     ? entry2.getKey().compareTo(entry1.getKey()) 
                                                     : entry1.getValue() - entry2.getValue()));
        
        for (Map.Entry entry : mp.entrySet()) {
            minHeap.add(entry);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        
        List<String> res = new LinkedList<>();
        while (!minHeap.isEmpty()) {
            res.add(minHeap.poll().getKey());
        }
        Collections.reverse(res);
        return res;
    }