【算法】【优选算法】优先级队列
目录
一、1046.最后一块石头的重量
题目链接：1046.最后一块石头的重量
题目描述：
题目解析：
- 题意就是让我们拿出提供的数组的最大两个值，大减小作差，将差值再放入数组，直到数组空了或者只有一个元素为止。
解题思路：
- 题目要求我们在一个乱序的数组中找最大两个值，我们首先想到数组排序，但是由于我们还需要将差值放入数组，我们放一次就需要排序一次。
- 使用优先级队列，大根堆，开销会小一些，我们只需要每次拿堆顶元素即可。
解题代码：
//时间复杂度 O(n)//空间复杂度 O(n)class Solution { public int lastStoneWeight(int[] stones) { //创建大根堆 PriorityQueue<Integer> queue = new PriorityQueue<>( (a,b) -> b - a ); //入堆 for(int i = 0; i < stones.length; i++) queue.offer(stones[i]); //执行逻辑 while(!queue.isEmpty() && queue.size() != 1) { int y = queue.poll(); int x = queue.poll(); queue.offer(y-x); } //返回值 return queue.isEmpty() ? 0 : queue.poll(); }}二、703. 数据流中的第 K 大元素
题目链接：703. 数据流中的第 K 大元素
题目描述：
题目解析：
- 给我们一个数组和一个数K，让我们在使用类的add方法后，返回数组中的第K大的数。
解题思路： - 我们使用一个大小为K的小根堆，那么我们剩下在堆中的数，就是数组中第K大到最大的值。
- 返回数组中的第K大的数，就是当前的堆顶。
解题代码：
//时间复杂度 O(nLogK)//空间复杂度 O(K)class KthLargest { PriorityQueue<Integer> heap; int param_1; public KthLargest(int k, int[] nums) { heap = new PriorityQueue<Integer>(); param_1 = k; for(int i = 0; i < nums.length; i++) { heap.offer(nums[i]); if(heap.size() > param_1) { heap.poll(); } } } public int add(int val) { heap.offer(val); if(heap.size() > param_1) { heap.poll(); } return heap.peek(); }}三、692. 前 K 个⾼频单词
题目链接：692. 前 K 个⾼频单词
题目描述：
题目解析：
- 给我们一个words的字符串数组，让我们返回数组中出现的频率次数最多到第K多的字符串。
- 当出现频次相同的时候，就直接按照字典顺序，字母前到后比较大小，大在前。
解题思路：
- 我们使用一个hash表，记录下字符串与其出现的次数。
- 在使用一个大小为K的堆，当我们的频次就是hash表中的value相同的时候，我们使用compare比较大小，创建的是大根堆，其余比较频次是小根堆。总体上看还是一个小根堆。
- 最后一次取出堆中的字符串即可，但是由于返回值又是从小到大，最后将结果数组逆序即可。
解题代码：
//时间复杂度：O(NLogK)//空间复杂U度：O(N)class Solution { public List<String> topKFrequent(String[] words, int k) { Map<String, Integer> hash = new HashMap<>(); PriorityQueue<Pair<String,Integer>> heap = new PriorityQueue<>( (a,b) -> { //频次相同大根堆 if(a.getValue().equals(b.getValue())) { return b.getKey().compareTo(a.getKey()); } //小根堆 return a.getValue() - b.getValue(); }); //hash初始化 for( String s : words) { hash.put(s, hash.getOrDefault(s ,0) + 1); } //入堆 for(Map.Entry<String, Integer> e : hash.entrySet()) { heap.offer(new Pair<>(e.getKey(),e.getValue())); if(heap.size() > k) { heap.poll(); } } //结果处理 List<String> ret = new ArrayList<String>(); while(!heap.isEmpty()) { ret.add(heap.poll().getKey()); } //逆置 Collections.reverse(ret); return ret; } }四、295. 数据流的中位数
题目链接：295. 数据流的中位数
题目描述：
- 就是让我们实现一个类，有初始化，添加元素（每次添加一个），查看元素中位数
题目解析：
- 我们只需要每次拿取类中的元素的时候，能够直接拿到中位数即可。
- 我们可以使用两个堆，小根堆记录数的中位数之后的部分，大根堆记录中位数的前半部分。
- 这样当元素个数是偶数个的时候，我们直接拿到两个堆的堆顶元素即可。为奇数个元素的时候，直接取出堆元素多的那个的堆顶元素即可。
解题思路：
- 我们使用两个堆，一个大根堆，一个小根堆，在记录下当前的元素个数。
- 当插入元素后，元素个数为偶数：
-
- 当插入元素比大根堆堆顶元素大：
-
-
- 大根堆中元素个数比小根堆多：直接将待插入元素插入小根堆即可。
-
-
-
- 大根堆中元素个数比小根堆少：将小根堆堆顶元素和待插入元素较小值，插入大根堆。另一个给小根堆。
-
-
- 当插入元素比大根堆堆顶元素小：
-
-
- 大根堆中元素个数比小根堆多：将大根堆堆顶元素插入小根堆。待插入元素给大根堆。
-
-
-
- 大根堆中元素个数比小根堆少：直接将待插入元素插入大根堆即可。
-
- 当插入元素后，元素个数为奇数：
-
- 当插入元素比大根堆堆顶元素大：插入小根堆。
-
- 当插入元素比大根堆堆顶元素小：插入大根堆。
解题代码：
//时间复杂度：O(LogN)//空间复杂度：O(N)class MedianFinder { //列表中元素个数 int n = 0; //大根堆记录前半部分值 PriorityQueue<Integer> big; //小根堆记录后半部分值 PriorityQueue<Integer> little; public MedianFinder() { big = new PriorityQueue<>((a,b) ->{ return b-a; }); little = new PriorityQueue<>(); } public void addNum(int num) { n += 1; if(n == 1 ) { big.offer(num); return; } //元素个数为偶数，比前面的大 if(n % 2 == 0 && big.peek() <= num) { //保持前后数据平衡 if(big.size() < little.size()) { //比后面小 if(!little.isEmpty() && little.peek() >= num) { big.offer(num); }else { int tmp = little.poll(); big.offer(tmp); little.offer(num); } }else { little.offer(num); } return; } //元素个数为偶数，比前面的小 if(n % 2 == 0 && big.peek() > num) { //保持前后数据平衡 if(big.size() < little.size()) { big.offer(num); }else { int tmp = big.poll(); big.offer(num); little.offer(tmp); } return; } //元素个数为奇数,比前面小 if(n % 2 != 0 && big.peek() >= num) { big.offer(num); } else { little.offer(num); } } public double findMedian() { if(n % 2 == 0) { return (double)((big.peek() + little.peek())/ 2.0); } if(big.size() > little.size()) { return big.peek(); } else { return little.peek(); } }}
