rustgym/leetcode/
_1338_reduce_array_size_to_the_half.rs

1struct Solution;
2use std::collections::BinaryHeap;
3use std::collections::HashMap;
4
5impl Solution {
6    fn min_set_size(arr: Vec<i32>) -> i32 {
7        let n = arr.len();
8        let mut hm: HashMap<i32, usize> = HashMap::new();
9        for x in arr {
10            *hm.entry(x).or_default() += 1;
11        }
12        let mut pq: BinaryHeap<usize> = BinaryHeap::new();
13        for (_, v) in hm {
14            pq.push(v);
15        }
16        let mut sum = 0;
17        let mut res = 0;
18        while sum * 2 < n {
19            sum += pq.pop().unwrap();
20            res += 1;
21        }
22        res
23    }
24}
25
26#[test]
27fn test() {
28    let arr = vec![3, 3, 3, 3, 5, 5, 5, 2, 2, 7];
29    let res = 2;
30    assert_eq!(Solution::min_set_size(arr), res);
31    let arr = vec![7, 7, 7, 7, 7, 7];
32    let res = 1;
33    assert_eq!(Solution::min_set_size(arr), res);
34    let arr = vec![1, 9];
35    let res = 1;
36    assert_eq!(Solution::min_set_size(arr), res);
37    let arr = vec![1000, 1000, 3, 7];
38    let res = 1;
39    assert_eq!(Solution::min_set_size(arr), res);
40    let arr = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
41    let res = 5;
42    assert_eq!(Solution::min_set_size(arr), res);
43}