2022-10-15:给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返
数组 一个 2022 10 可以 出现 元素 返回
2023-06-13 09:14:40 时间
2022-10-15:给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。
你可以按 任意顺序 返回答案。
要求时间复杂度O(N)。
输入: nums = [1,1,1,2,2,3], k = 2。
输出: [1,2]。
答案2022-10-15:
力扣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 {}
执行结果如下:
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_07_3_week/Code03_TopKFrequentElements.java)
相关文章
- 2022-09-11:arr是一个可能包含重复元素的整数数组,我们将这个数组分割成几个“块”, 并将这些块分别进行排序。之后再连接起来,使得连接的结果和按升序排
- 2022-10-27:设计一个数据结构,有效地找到给定子数组的 多数元素 。 子数组的 多数元素 是在子数组中出现 threshold 次数或次数以上的元素。
- 将多层级数组转化为一级数组(即提取嵌套数组元素最终合并为一个数组)
- 2022-10-30:给你一个长度为 n 的整数数组 rolls 和一个整数 k 。 你扔一个 k 面的骰子 n 次,骰子的每个面分别是 1 到 k , 其中第
- 2022-10-21:你将得到一个整数数组 matchsticks ,其中 matchsticks[i] 是第 i 个火柴棒的长
- 2022-10-23:给你一个整数数组 nums 。如果 nums 的一个子集中,所有元素的乘积可以表示为一个或多个 互不相同的
- 2022-12-18:给定一个长度为n的二维数组graph,代表一张图, graph[i] = {a,b,c,d} 表示i讨厌(a,b,c,d),讨厌关系为双向
- JavaScript数组
- 2022-11-03:给定一个数组arr,和一个正数k如果arr[i] == 0,表示i这里既可以是左括号也可以是右括号,而且可
- 2022-11-18:给定一个数组arr,表示连续n天的股价,数组下标表示第几天指标X:任意两天的股价之和 - 此两天间隔的天数
- 2022-12-18:给定一个长度为n的二维数组graph,代表一张图,graph[i] = {a,b,c,d} 表示i讨厌(a
- 2022-12-22:给定一个数字n,代表数组的长度,给定一个数字m,代表数组每个位置都可以在1~m之间选择数字,所有长度为n的
- 【算法】js求一个数组的幂集
- 2022-04-23:给定你一个整数数组 nums 我们要将 nums 数组中的每个元素移动到 A 集合 或者 B 集合中 使得 A 集合和 B 集合不为空,并
- 关于二维数组分解为一维数组进行操作详解编程语言
- MySQL 数组,提高数据处理效率的必备工具(mysql数组)
- php下将多个数组合并成一个数组的方法与实例代码