力扣 | 215. 数组中的第K个最大元素
2023-12-19 20:53:40
/* leetcode 347 号算法题:前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。
你可以按 任意顺序 返回答案。
输入: nums = [1,1,1,2,2,3], k = 2
输出: [2, 1]
输入: nums = [1], k = 1
输出: [1]
1 <= nums.length <= 10^5
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的
进阶:你所设计算法的时间复杂度 必须 优于 O(n log n) ,其中 n 是数组大小。
*/
首先,我们来对比一下PriorityQueue的add()和offer()方法的主要区别: 方法 描述 抛出异常 返回特殊值
add() 向队列中添加元素 是 否 offer() 向队列中添加元素 否 是
从表格可以看出,add()方法方法则不会抛出异常在向队列中添加元素时,如果队列已满,则会抛出异常。而offer(),而是返回一个特殊值,通常是true或false,用于表示元素是否成功添加到队列中。因此,在使用过程中,我们需要根据具体需求选择使用哪个方法。
import java.util.PriorityQueue;
public class Problem_215_FindKthLargestNum {
public int findKthLargestNum(int [] nums,int k){
PriorityQueue<Integer> pq = new PriorityQueue<>(k);
for (int i = 0; i < k; i++) {
pq.add(nums[i]);
}
for (int i = k; i < nums.length; i++) {
if(nums[i] > pq.peek()){
pq.remove();
pq.add(nums[i]);
}
}
return pq.remove();
}
//第二种方式!
public int findKthLargestNum1(int [] nums,int k){
PriorityQueue<Integer> pq = new PriorityQueue<>(k + 1);
for (int i = 0; i < nums.length; i++) {
pq.add(nums[i]);
if(pq.size() > k){
pq.remove();
}
}
return pq.remove();
}
}
文章来源:https://blog.csdn.net/qq_37247026/article/details/135091779
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!