【重点!!!】【堆】215.数组中的第K个最大元素
2023-12-25 05:57:18
法1:小根堆
最大的K个元素 => 小根堆(类似上窄下宽的梯形)
最小的K个元素 => 大根堆(类似倒三角形)
必须掌握!!!
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> q = new PriorityQueue<>();
for (int i = 0; i < k; ++i) {
q.offer(nums[i]);
}
for (int i = k; i < nums.length; ++i) {
if (nums[i] > q.peek()) {
q.poll();
q.offer(nums[i]);
}
}
return q.peek();
}
}
法2:基于快排
class Solution {
public int findKthLargest(int[] nums, int k) {
List<Integer> list = new ArrayList<>();
for (int i : nums) {
list.add(i);
}
return quickSelect(list, k);
}
public int quickSelect(List<Integer> list, int k) {
int n = list.size();
Random rand = new Random();
int rInx = rand.nextInt(n); // 生成0 ~ n-1之间的整数
List<Integer> big = new ArrayList<>();
List<Integer> same = new ArrayList<>();
List<Integer> small = new ArrayList<>();
for (int i = 0; i < n; ++i) {
if (list.get(i) > list.get(rInx)) {
big.add(list.get(i));
} else if (list.get(i) == list.get(rInx)) {
same.add(list.get(i));
} else {
small.add(list.get(i));
}
}
if (big.size() >= k) {
return quickSelect(big, k);
} else if (k > (big.size() + same.size())) {
return quickSelect(small, k - (big.size() + same.size()));
} else {
return list.get(rInx);
}
}
}
文章来源:https://blog.csdn.net/Allenlzcoder/article/details/135189918
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!