Question

How to find K most frequent elements in an unsorted array with Rust

Answer 1

#![allow(non_snake_case)]

use std::hash::Hash;
use std::cmp::{Eq, Ord, Reverse};
use std::collections::{BinaryHeap, HashMap};

fn findKMostFrequentElements<T>(arr: &[T], k: usize) -> Vec<(usize, &T)>
where
    T: Hash + Eq + Ord,
{
    let mut map = HashMap::new();
    for n in arr {
        *map.entry(n).or_default() += 1;
    }

    let mut heap = BinaryHeap::with_capacity(k + 1);
    for (n, count) in map.into_iter() {
        heap.push(Reverse((count, n)));
        if heap.len() > k {
            heap.pop();
        }
    }
    heap.into_sorted_vec().into_iter().map(|r| r.0).collect()
}

fn main() {
    let arr = [4, 5, 19, 50, 7, 19, 8, 19, 3, 3, 6, 3, 27, 19, 3, 3];
    let k = 2;
    
    println!("{:?}", findKMostFrequentElements(&arr, k))
}




/*
run:

[(5, 3), (4, 19)]

*/

 

70+ SQL courses for beginners and professionals