RUST GYM Leetcode 347 Top K Frequent Elements Rust Solution

347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Note:

You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
It's guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
You can return the answer in any order.

Rust Solution

struct Solution;
use std::cmp::Reverse;
use std::collections::BinaryHeap;
use std::collections::HashMap;

type Pair = (Reverse<usize>, i32);

impl Solution {
    fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let k = k as usize;
        let mut hm: HashMap<i32, usize> = HashMap::new();
        let mut pq: BinaryHeap<Pair> = BinaryHeap::new();
        for x in nums {
            *hm.entry(x).or_default() += 1;
        }
        for (x, f) in hm {
            pq.push((Reverse(f), x));
            if pq.len() > k {
                pq.pop();
            }
        }
        pq.into_iter().map(|p| p.1).rev().collect()
    }
}

#[test]
fn test() {
    let nums = vec![1, 1, 1, 2, 2, 3];
    let k = 2;
    let res = vec![1, 2];
    assert_eq!(Solution::top_k_frequent(nums, k), res);
}

Having problems with this solution? Click here to submit an issue on github.