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.