算法与数据结构——返回流式数据的第K大元素

返回流式数据的第K大元素

思路：

1、思考返回最大数据的思路，维护一个最大值，每次进来的元素和最大值比较，则能找到最大值2、如果把最大值换成第K大元素，维护一个前K大的排序数组，每次进来的元素和第K位值比较，如果比第K位的值大，则把第K位的元素踢出排序数组，把刚才的比较值加入排序数组再次排序3、可以使用最小顶堆来实现这个排序数组，因为最小顶堆的堆顶永远是堆的最小值

时间复杂度 O(n)*O(log2K)

/** * @author lxd * @version 1.0.0 * @create 2020-07-04 16:42 * @desc 返回流式数据的第K大元素 **/ public class KthLargestElementDemo { /**** * 思路： * 1、思考返回最大数据的思路，维护一个最大值，每次进来的元素和最大值比较，则能找到最大值 * 2、如果把最大值换成第K大元素，维护一个前K大的排序数组，每次进来的元素和第K位值比较，如果比第K位的值大，则把第K位的元素踢出排序数组，把刚才的比较值加入排序数组再次排序 * 3、可以使用最小顶堆来实现这个排序数组，因为最小顶堆的堆顶永远是堆的最小值 * */ private static class KthLargestElement { private int k; private PriorityQueue<Integer> priorityQueue; public KthLargestElement(int k, PriorityQueue<Integer> priorityQueue) { this.k= k; this.priorityQueue = priorityQueue; } private void getKthLargestEle(int [] arrays){ for (int item: arrays) { add(item); } } /**** * 新增元素校验 * @param item */ private void add(int item) { /*** * 1、堆的size小于K，直接往堆添加元素 * 2、如果新增的元素比堆顶元素大，移除当前对顶元素，添加新的元素进堆 */ if(priorityQueue.size()<k){ priorityQueue.offer(item); }else if (item > priorityQueue.peek()){ priorityQueue.poll(); priorityQueue.offer(item); } } } public static void main(String[] args) { int k=3; PriorityQueue<Integer> priorityQueue =new PriorityQueue<>(); KthLargestElement kthLargestElement =new KthLargestElement(k,priorityQueue); int [] arrays= {1,6,8,9,4,5,3,10,7}; kthLargestElement.getKthLargestEle(arrays); System.out.println("第K大元素:"+priorityQueue.peek()); }