aboutsummaryrefslogtreecommitdiff
path: root/top_k_freq_words.rs
blob: 606c237b3f87fded3cb6623acf34b39854412ba2 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
use std::collections::BinaryHeap;
use std::collections::HashMap;

struct Solution;

impl Solution {
    pub fn top_k_frequent(words: Vec<String>, k: i32) -> Vec<String> {
        let mut word_to_freq = HashMap::<String, i32>::new();
        for w in words {
            *word_to_freq.entry(w).or_default() += 1;
        }
        let mut heap = BinaryHeap::<(i32, String)>::new();
        for (word, freq) in word_to_freq {
            heap.push((-freq, word));
            if heap.len() > k as usize {
                heap.pop();
            }
        }
        let mut ans: Vec<String> = vec![];
        while let Some((_freq, word)) = heap.pop() {
            ans.push(word);
        }
        ans.reverse();
        ans
    }
}