数组中的第K个最大元素
解法一
暴力
先排序再返回
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个高频元素
解法一
优先队列
先遍历获取频数数组再回去前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; } }
