347. Top K Frequent Elements

Description of the Problem

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

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

Example 2:

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

Constraints:

1 <= nums.length <= 10^5
10^4 <= nums[i] <= 10^4
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.

Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

Count the number of occurrence of each number. Insert them into bounded-size min heap according to their number of occurrence. Since each insertion remove element with the smallest number of occurrence if the min heap is full, the remaining elements in the heap must be the Top K most-frequent elements.

Code

use std::collections::{HashMap, BinaryHeap};

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

impl Ord for Counter {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering{
        other.1.cmp(&self.1)
    }
}

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

impl Solution {
    pub fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let k = k as usize;
        let mut counterMap = HashMap::new();
        nums.into_iter().for_each(
            |n| {
                let mut count = counterMap.get_mut(&n);
                if count.is_none(){
                    counterMap.insert(n,1);
                }else{
                    *count.unwrap() += 1;
                }
            }
        );

        let mut min_heap = BinaryHeap::new();

        counterMap.into_iter().for_each(
            |(key,val)| {
                min_heap.push(Counter(key,val));
                if min_heap.len() > k {
                    min_heap.pop();
                }
            }
        );
        
        return min_heap.into_iter().rev().map(|Counter(v,_)| v ).collect::<Vec<i32>>();
    }
}

Complexity (n is the size of array)

Time complexity:

Worst case: \(O(n + n \log k)\)
- \( n \) for counting
- \(\log k\) for insertion of an element in bounded min heap

Auxiliary Space:

\( O(n) \)
- The size of counter is bound by the number of elements.

Leetbook