👨💻个人主页: 才疏学浅的木子 🙇♂️ 本人也在学习阶段如若发现问题,请告知非常感谢 🙇♂️ 📒 本文来自专栏: 算法 🌈 算法类型:Hot100题 🌈
解法一
暴力 先排序再返回
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length-k];
}
}
解法二
优先队列 维护一个长度为k的小根堆
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> p = new PriorityQueue<Integer>(k);
for(int i = 0;i < nums.length;i++){
if(p.size() == k){
if(p.peek() < nums[i]){
p.poll();
p.add(nums[i]);
}
continue;
}else{
p.add(nums[i]);
}
}
return p.poll();
}
}
解法一
滑动窗口 滑动窗口维护一个nums[i]值递减的序列
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
if(k == 1 || len == 1 || len < k) return nums;
LinkedList<Integer> list = new LinkedList<>();
// 维护一个降序的双向队列
// 【1,3,-1】 = > [3,-1] =》[1,2]//下标
for(int i = 0;i < k;i++){
while(!list.isEmpty() && nums[i] > nums[list.peekLast()]){
list.pollLast();
}
list.addLast(i);
}
int ans[] = new int[len-k+1];
ans[0] = nums[list.peekFirst()];
for(int i = k;i < len;i++){
while(!list.isEmpty() && nums[i] > nums[list.peekLast()]){
list.pollLast();
}
list.addLast(i);
// 避免越界
while(!list.isEmpty() && list.peekFirst() <= i-k){
list.pollFirst();
}
ans[i-k+1] = nums[list.peekFirst()];
}
return ans;
}
}
解法一
优先队列 先遍历获取频数数组再回去前k个
class Solution {
public int[] topKFrequent(int[] nums, int k) {
HashMap<Integer,Integer> map = new HashMap<>();
for(int i = 0;i < nums.length;i++){
map.put(nums[i],map.getOrDefault(nums[i],0)+1);
}
PriorityQueue<Integer> p = new PriorityQueue<Integer>((num1,num2)->{
return map.get(num1) - map.get(num2);
});
map.forEach((key,value)->{
if(p.size() < k){
p.add(key);
}else{
if(map.get(p.peek()) < map.get(key)){
p.poll();
p.add(key);
}
}
});
int ans [] = new int[k];
int j = 0;
while(!p.isEmpty()){
ans[j++] = p.poll();
}
return ans;
}
}