给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。
你可以按 任意顺序 返回答案。
要求时间复杂度O(N)。
输入: nums = [1,1,1,2,2,3], k = 2。
输出: [1,2]。
力扣347。词频统计，bfprt算法。
力扣上测试了主流语言的运行速度和内存占用。运行速度上，rust最快，go最慢，但跟java差不多。内存占用上，rust最少，go比rust稍微多一点，java最多。
代码用rust编写。代码如下：
use rand::Rng;
use std::{collections::HashMap, iter::repeat};
impl Solution {
pub fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> {
let mut map: HashMap<i32, i32> = HashMap::new();
for num in nums.iter() {
map.insert(
*num,
if map.contains_key(num) {
*map.get(num).unwrap()
} else {
0
} + 1,
);
}
let mut i = map.len() as i32;
let mut arr: Vec<Vec<i32>> = repeat(repeat(0).take(2).collect())
.take(i as usize)
.collect();
for (key, value) in map.iter() {
i -= 1;
arr[i as usize][0] = *key;
arr[i as usize][1] = *value;
}
let arr_len = arr.len() as i32;
Solution::more_less(&mut arr, 0, arr_len - 1, k);
let mut ans: Vec<i32> = repeat(0).take(k as usize).collect();
while i < k {
ans[i as usize] = arr[i as usize][0];
i += 1;
}
return ans;
}
fn more_less(arr: &mut Vec<Vec<i32>>, l: i32, r: i32, k: i32) {
if k == r - l + 1 {
return;
}
arr.swap(
r as usize,
(l + rand::thread_rng().gen_range(0, r - l + 1)) as usize,
);
let pivot = Solution::partition(arr, l, r);
if pivot - l == k {
return;
} else if pivot - l > k {
Solution::more_less(arr, l, pivot - 1, k);
} else {
Solution::more_less(arr, pivot, r, k - pivot + l);
}
}
fn partition(arr: &mut Vec<Vec<i32>>, l: i32, r: i32) -> i32 {
let mut left = l - 1;
let mut index = l;
while index < r {
if arr[index as usize][1] <= arr[r as usize][1] {
index += 1;
} else {
left += 1;
arr.swap(left as usize, index as usize);
index += 1;
}
}
left += 1;
arr.swap(left as usize, r as usize);
return left;
}
}
fn main() {
let num2 = vec![1, 1, 1, 2, 2, 3];
let k = 2;
let ans = Solution::top_k_frequent(num2, k);
println!("ans = {:?}", ans);
}
struct Solution {}执行结果如下：
