2022-10-15:给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。 你可以按 任意顺序 返回答案。
数组 一个 2022 10 可以 出现 元素 返回
2023-06-13 09:13:53 时间
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 {}
执行结果如下:
相关文章
- 2022-09-23:整数数组 stations 表示 水平数轴 上各个加油站的位置。给你一个整数 k 。 请你在数轴上增设 k 个加油站, 新增加油站可以位于
- 2022-10-21:你将得到一个整数数组 matchsticks ,其中 matchsticks[i] 是第 i 个火柴棒的长度。 你要用 所有的火柴棍 拼成
- 2022-10-23:给你一个整数数组 nums 。如果 nums 的一个子集中, 所有元素的乘积可以表示为一个或多个 互不相同的质数 的乘积,那么我们称它为
- 2022-10-27:设计一个数据结构,有效地找到给定子数组的 多数元素 。 子数组的 多数元素 是在子数组中出现 threshold 次数或次数以上的元素。
- 2022-11-04:给定一个正数n,表示有多少个节点 给定一个二维数组edges,表示所有无向边 edges[i] = {a, b} 表示a到b有一条无向边
- java中数组的输出方法_java将一个数组逆序输出
- 【JAVA冷知识】既然数组是一个类,为什么动态加载不适合数组?如何动态加载一个数组?
- 2022-12-18:给定一个长度为n的二维数组graph,代表一张图, graph[i] = {a,b,c,d} 表示i讨厌(a,b,c,d),讨厌关系为双向
- 2022-11-03:给定一个数组arr,和一个正数k如果arr[i] == 0,表示i这里既可以是左括号也可以是右括号,而且可
- 2023-01-12:一个n*n的二维数组中,只有0和1两种值,当你决定在某个位置操作一次,那么该位置的行和列整体都会变成1,不
- 2023-01-14:给定一个二维数组map,代表一个餐厅,其中只有0、1两种值map[i][j] == 0 表示(i,j)位置
- java多维数组
- 【算法】js求一个数组的幂集
- PHP end():将数组内部指针指向最后一个元素
- MySQL中定义及操作数组的方法(mysql定义数组)
- MySQL的一维数组操作简介(mysql一维数组使用)
- PHP中通过加号合并数组的一个简单方法分享
- 求数组最大最小值方法适用于任何数组
- 向一个数组中插入一个1~100的随机数
- PHP获取数组最后一个值的2种方法