find the kth least common element in an array in rust

To find the kth least common element in an array in Rust, we can make use of sorting and binary search algorithms.

First, we will sort the array in increasing order. After that, we will iterate through the array and maintain a count of the number of occurrences of each element.

Next, we will sort the counts in increasing order and perform a binary search on the counts array to find the kth least common element.

Here's the Rust code for the same:


main.rs
fn find_kth_least_common_element(arr: &[i32], k: usize) -> Option<i32> {
    let n = arr.len();
    if k > n {
        return None;
    }

    // Sort the array
    let mut sorted_arr = arr.to_vec();
    sorted_arr.sort_unstable();

    // Find the counts of all elements
    let mut freq_map = std::collections::HashMap::new();
    for i in 0..n {
        let count = freq_map.entry(sorted_arr[i]).or_insert(0);
        *count += 1;
    }

    // Sort the counts and perform binary search
    let mut counts: Vec<usize> = freq_map.values().copied().collect();
    counts.sort_unstable();
    let sz = counts.len();
    if k > counts[sz - 1] {
        return None;
    }

    let mut l = 0usize;
    let mut r = sz - 1usize;
    while l < r {
        let mid = (l + r) / 2;
        if counts[mid] >= k {
            r = mid;
        } else {
            l = mid + 1;
        }
    }

    // Return the element corresponding to the kth least count
    let kth_count = counts[l];
    let mut cnt = 0usize;
    for (k, v) in freq_map.iter() {
        cnt += *v;
        if cnt >= kth_count {
            return Some(*k);
        }
    }
    None
}

fn main() {
    let arr = [1, 1, 2, 2, 3, 4, 5, 5, 5, 5];
    let k = 4;
    match find_kth_least_common_element(&arr[..], k) {
        Some(val) => println!("The {}th least common element is {}", k, val),
        None => println!("No solution exists"),
    }
}
1408 chars
57 lines

Here, we have a function find_kth_least_common_element that takes an array and an integer k as input and returns an Option<i32>.

If there exists a kth least common element, it returns Some(val) where val is the kth least common element. If there is no such element, it returns None.

In the main function, we have created an array arr and an integer k. We called the find_kth_least_common_element function with these inputs and printed the result. The output of the code is The 4th least common element is 2.

similar rust code snippets

find the kth most common element in an array in rust

find the kth least common element in an array in rust

find the kth least frequent element in an array in rust

find the kth most 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