find the kth most frequent element in an array in rust

One way to find the kth most frequent element in an array is to use a hash map to count the frequencies of each element, sort the hash map by value in descending order, and return the kth key. Another approach is to use a min heap to keep track of the k most frequent elements, where the root of the heap is the minimum frequency seen so far.

Here's the implementation of the first approach:


main.rs
use std::collections::HashMap;

fn kth_most_frequent_element(arr: &[i32], k: usize) -> Option<i32> {
    let mut freq: HashMap<i32, usize> = HashMap::new();
    for &n in arr {
        *freq.entry(n).or_default() += 1;
    }
    
    let mut freq_vec: Vec<(i32, usize)> = freq.into_iter().collect();
    freq_vec.sort_by_key(|&(_, count)| count);
    freq_vec.reverse();
    
    if let Some(&(kth_elem, _)) = freq_vec.get(k - 1) {
        Some(kth_elem)
    } else {
        None
    }
}

fn main() {
    let arr = [1, 2, 2, 3, 3, 3];
    let k = 2;
    let kth_elem = kth_most_frequent_element(&arr, k).unwrap();
    println!("The {}th most frequent element in {:?} is {}", k, arr, kth_elem);
}
697 chars
26 lines

And here's the implementation of the second approach using a min heap:


main.rs
use std::collections::{HashMap, BinaryHeap};
use std::cmp::{Ordering, Reverse};

#[derive(Eq, PartialEq)]
struct Freq(i32, usize);

impl Ord for Freq {
    fn cmp(&self, other: &Self) -> Ordering {
        self.0.cmp(&other.0)
    }
}

impl PartialOrd for Freq {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn kth_most_frequent_element(arr: &[i32], k: usize) -> Option<i32> {
    let mut freq: HashMap<i32, usize> = HashMap::new();
    for &n in arr {
        *freq.entry(n).or_default() += 1;
    }
    
    let mut pq: BinaryHeap<Reverse<Freq>> = BinaryHeap::new();
    for (num, count) in freq {
        if pq.len() < k {
            pq.push(Reverse(Freq(num, count)));
        } else if pq.peek().unwrap().0 < Freq(num, count) {
            pq.pop();
            pq.push(Reverse(Freq(num, count)));
        }
    }
    
    if let Some(Reverse(Freq(kth_elem, _))) = pq.peek() {
        Some(kth_elem)
    } else {
        None
    }
}

fn main() {
    let arr = [1, 2, 2, 3, 3, 3];
    let k = 2;
    let kth_elem = kth_most_frequent_element(&arr, k).unwrap();
    println!("The {}th most frequent element in {:?} is {}", k, arr, kth_elem);
}
1204 chars
48 lines

similar rust code snippets

find the kth most frequent element in an array in rust

find the kth least common element in an array in rust

find the kth most common element in an array in rust

find the kth least frequent element in an array in rust

remove an element from the beginning of an array in rust

find the index of an element in an array in rust

insert an element into an array at a specific index in rust

remove an element from the middle of an array in rust

remove an element from an array at a specific index in rust

remove an element from the end of an array in rust

related categories