347. 前 K 个高频元素

题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

解题思路

#![allow(unused)]
fn main() {
struct Solution {}
#[derive(PartialEq, Eq)]
struct Y { a: i32, b: usize, }
type Z = Y;
use std::cmp::Ordering;
impl PartialOrd<Z>for Z{fn partial_cmp(&self,o:&Z)->Option<Ordering>{Some(self.cmp(o))}}
impl Ord for Z{fn cmp(&self,o:&Z)->Ordering{o.b.cmp(&self.b)}}
impl Solution {
    pub fn top_k_frequent(v: Vec<i32>, k: i32) -> Vec<i32> {
        use std::collections::HashMap;
        use std::collections::BinaryHeap;
        let mut m: HashMap<i32, usize> = HashMap::new();
        let mut q: BinaryHeap<Z> = BinaryHeap::new();
        for i in v {
            *m.entry(i).or_default() += 1;
        }
        for (a, b) in m {
            q.push(Z {a:a, b:b});
            if q.len() > k as usize { q.pop(); }
        }
        let mut res = vec![];
        for i in q {
            res.push(i.a);
        }
        res
    }
}
}

学习感想

map+小顶堆

#![allow(unused)]
fn main() {
struct Solution {}

impl Solution {
    pub fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> {
        use std::collections::{HashMap, BinaryHeap};
        let mut map: HashMap<i32, usize> = HashMap::new();
        nums.iter().for_each(|&i| {
            map.entry(i).and_modify(|x| *x += 1usize).or_default();
        });
        let mut res: Vec<i32> = Vec::new();
        let mut pq: BinaryHeap<(usize, i32)> = BinaryHeap::new();
        for (k, v) in map {
            pq.push((v, k));
        }
        (0i32 .. k) .for_each(|_| {
            res.push(pq.pop().unwrap().1);
        });
        res
    }
}


}