【算法】【优选算法】优先级队列
目录
一、1046.最后一块石头的重量
题目链接：1046.最后一块石头的重量
题目描述：
题目解析：
- 题意就是让我们拿出提供的数组的最大两个值，大减小作差，将差值再放入数组，直到数组空了或者只有一个元素为止。
解题思路：
- 题目要求我们在一个乱序的数组中找最大两个值，我们首先想到数组排序，但是由于我们还需要将差值放入数组，我们放一次就需要排序一次。
- 使用优先级队列，大根堆，开销会小一些，我们只需要每次拿堆顶元素即可。
解题代码：
//时间复杂度 O(n)//空间复杂度 O(n)classSolution{publicintlastStoneWeight(int[] stones){//创建大根堆PriorityQueue<Integer> queue =newPriorityQueue<>((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)classKthLargest{PriorityQueue<Integer> heap;int param_1;publicKthLargest(int k,int[] nums){ heap =newPriorityQueue<Integer>(); param_1 = k;for(int i =0; i < nums.length; i++){ heap.offer(nums[i]);if(heap.size()> param_1){ heap.poll();}}}publicintadd(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)classSolution{publicList<String>topKFrequent(String[] words,int k){Map<String,Integer> hash =newHashMap<>();PriorityQueue<Pair<String,Integer>> heap =newPriorityQueue<>((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(newPair<>(e.getKey(),e.getValue()));if(heap.size()> k){ heap.poll();}}//结果处理List<String> ret =newArrayList<String>();while(!heap.isEmpty()){ ret.add(heap.poll().getKey());}//逆置Collections.reverse(ret);return ret;}}四、295. 数据流的中位数
题目链接：295. 数据流的中位数
题目描述：
- 就是让我们实现一个类，有初始化，添加元素（每次添加一个），查看元素中位数
题目解析：
- 我们只需要每次拿取类中的元素的时候，能够直接拿到中位数即可。
- 我们可以使用两个堆，小根堆记录数的中位数之后的部分，大根堆记录中位数的前半部分。
- 这样当元素个数是偶数个的时候，我们直接拿到两个堆的堆顶元素即可。为奇数个元素的时候，直接取出堆元素多的那个的堆顶元素即可。
解题思路：
- 我们使用两个堆，一个大根堆，一个小根堆，在记录下当前的元素个数。
- 当插入元素后，元素个数为偶数：
- 当插入元素比大根堆堆顶元素大：
- 大根堆中元素个数比小根堆多：直接将待插入元素插入小根堆即可。
- 大根堆中元素个数比小根堆少：将小根堆堆顶元素和待插入元素较小值，插入大根堆。另一个给小根堆。
- 当插入元素比大根堆堆顶元素小：
- 大根堆中元素个数比小根堆多：将大根堆堆顶元素插入小根堆。待插入元素给大根堆。
- 大根堆中元素个数比小根堆少：直接将待插入元素插入大根堆即可。
- 当插入元素后，元素个数为奇数：
- 当插入元素比大根堆堆顶元素大：插入小根堆。
- 当插入元素比大根堆堆顶元素小：插入大根堆。
解题代码：
//时间复杂度：O(LogN)//空间复杂度：O(N)classMedianFinder{//列表中元素个数int n =0;//大根堆记录前半部分值PriorityQueue<Integer> big;//小根堆记录后半部分值PriorityQueue<Integer> little;publicMedianFinder(){ big =newPriorityQueue<>((a,b)->{return b-a;}); little =newPriorityQueue<>();}publicvoidaddNum(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);}}publicdoublefindMedian(){if(n %2==0){return(double)((big.peek()+ little.peek())/2.0);}if(big.size()> little.size()){return big.peek();}else{return little.peek();}}}
