一.数组中的第K个最大元素问题概述给定整数数组nums和整数k请返回数组中第k个最大的元素。请注意你需要找的是数组排序后的第k个最大的元素而不是第k个不同的元素。你必须设计并实现时间复杂度为O(n)的算法解决此问题。思路Hoare 分区就是找排完序没有去重的第K个最大元素。也就是找索引为n-k的数。要求O(n)就是排序算法上选优这里采用类似快排的算法。快排核心思想选择一个数作为基数剩下的数进行划分比它小的放左边比它大的放右边。之后递归在左右区间继续这样操作。代码上实现使用2个指针i从左扫到第一个大于它的位置j从右扫到第一个小于它的位置然后进行交换。如果ij那么i左边都小于哨兵i右边都大于哨兵此刻交换哨兵。【看图写代码-快速排序交换法挖空法】https://www.bilibili.com/video/BV1pd4y1z7gf?vd_source1d2dfd176f1f132070d67162d5977008本题难点是边界条件硬记就行用do是因为交换后还是需要走一步的用do方便。这个当中的意思是如果k在某一边的区域只需要对这个区域进行排序快速选择代码class Solution { public int findKthLargest(int[] nums, int k) { int nnums.length; return qsel(nums,0,n-1,n-k); } private int qsel(int[] nums,int l,int r,int k){ if(lr){ return nums[k]; } int il-1,jr1; int xnums[l]; while(ij){ do i;while(nums[i]x); do j--;while(nums[j]x); if(ij){ int tempnums[i]; nums[i]nums[j]; nums[j]temp; } } if(kj){ return qsel(nums,l,j,k); }else{ return qsel(nums,j1,r,k); } } }二.前K个高频元素问题概述给你一个整数数组nums和一个整数k请你返回其中出现频率前k高的元素。你可以按任意顺序返回答案思路采用最小堆的方法频率小的放最上面当元素个数超过k个就把小头给切掉。最后输出即可。本代码中是按频率从大到小进行输出的其实也可以不用这么输出题目没做要求。frequencyMap.getOrDefault(num,0): 尝试从frequencyMap中获取键num对应的值如果num存在返回其当前频率值如果num不存在返回默认值0.offer()将元素插入堆中.poll(): 移除堆顶并返回.peek(): 查看堆顶不移除.size(): 查看堆大小 .isEmpty(): 判断堆是否为空代码class Solution { public int[] topKFrequent(int[] nums, int k) { MapInteger,Integer frequencyMapnew HashMap(); for(int num:nums){ frequencyMap.put(num,frequencyMap.getOrDefault(num,0)1); } PriorityQueueInteger minHeapnew PriorityQueue( (a,b)-frequencyMap.get(a)-frequencyMap.get(b) ); for(int num:frequencyMap.keySet()){ minHeap.offer(num); if(minHeap.size()k){ minHeap.poll(); } } int[] resultnew int[k]; for(int ik-1;i0;i--){ result[i]minHeap.poll(); } return result; } }三.数据流的中位数问题概述你需要设计一个类MedianFinder它有两个方法addNum(int num)接收一个整数添加到数据结构中findMedian()返回当前所有数字的中位数关键难点数字是流式添加的你不知道总共会有多少数字也不知道数字的顺序但每次调用findMedian()都要能快速返回当前的中位数。思路不知道总数是奇数还是偶数采用堆的思想在加入的过程中进行动态排序分为俩部分左部分为大根堆右部分为小根堆如果俩堆数量相等就是偶数取俩堆的顶相加除2.0即可如果数量不等就是奇数这里为了方便让大根堆的数量大一些如果大根堆数量-小根堆数量1进行调整如果小根堆数量小于大根堆数量也需要调整。始终保持大根堆数量和小根堆的数量差在1以内并且大根堆最大值小于小根堆最小值。代码class MedianFinder { private PriorityQueueInteger minHeap; private PriorityQueueInteger maxHeap; public MedianFinder() { maxHeapnew PriorityQueueInteger((a,b)-b-a); minHeapnew PriorityQueueInteger(); } public void addNum(int num) { if(maxHeap.isEmpty()||nummaxHeap.peek()){ maxHeap.offer(num); if(maxHeap.size()minHeap.size()1){ minHeap.offer(maxHeap.poll()); } }else{ minHeap.offer(num); if(minHeap.size()maxHeap.size()){ maxHeap.offer(minHeap.poll()); } } } public double findMedian() { if(maxHeap.size()minHeap.size()){ return (maxHeap.peek()minHeap.peek())/2.0; }else{ return maxHeap.peek(); } } } /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder obj new MedianFinder(); * obj.addNum(num); * double param_2 obj.findMedian(); */