347. Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. The answer may be returned 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]

Bucket by frequency:

#![allow(unused)]
fn main() {
// time O(n), space O(n)
pub fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> {
    let k = k as usize;
    let mut count = HashMap::new();
    let mut freq = vec![vec![]; nums.len() + 1];
    for &num in &nums {
        *count.entry(num).or_insert(0usize) += 1;
    }

    for (&num, &cnt) in &count {
        freq[cnt].push(num);
    }

    let mut res = Vec::new();
    for i in (1..freq.len()).rev() {
        for &num in &freq[i] {
            res.push(num);
            if res.len() == k {
                return res;
            }
        }
    }

    res
}
}

Min-heap of size k:

#![allow(unused)]
fn main() {
// time O(n log k), space O(n)
pub fn top_k_frequent_heap(nums: Vec<i32>, k: i32) -> Vec<i32> {
    let k = k as usize;
    let mut count = HashMap::new();
    for &num in &nums {
        *count.entry(num).or_insert(0i32) += 1;
    }

    let mut heap = BinaryHeap::new();
    for (&num, &freq) in &count {
        heap.push(Reverse((freq, num)));
        if heap.len() > k {
            heap.pop();
        }
    }

    heap.into_iter().map(|Reverse((_, num))| num).collect()
}
}