算法通关村14关 | 堆在数组中找第k大的元素应用

1. 在数组中找第k大元素

题目

LeetCode215：给定整数数组nums和整数k，请返回数组中第k个最大的元素，

思路

解题思路用三个，选择法，堆查找和快速排序。

我们选择用大堆小堆解决问题，“找最大用小堆，找最小用大堆，找中间用两个堆”，我们构造一个大小只有4的小根堆，为了更好的说明情况，我们扩展一下题目序列[3,2,3,1,2,4,5,1,5,6,2,3]。

堆满了之后，只有大于根节点的元素才能入堆，否则就直接抛弃，元素进入堆中，需要调换位置，满足最小堆的结构，如果发现两个子树都小，则应该和最小的元素交换，如果都一样，则随便选一个。

需要注意：堆不满则直接添加；堆满的时候读到大于根节点的元素才将堆顶拿出，放入新读到的数。

代码

我们用的是Javajdk中的PriorityQueue构建最小堆

    /*** 用最小堆在数组中找第k大的元素* @param nums* @param k* @return*/public int findkLargest(int[] nums, int k){if (k > nums.length){return -1;}int len = nums.length;//创建一个含有k个元素的最小堆PriorityQueue<Integer> minHeap = new PriorityQueue<>(k,(a,b) -> (a - b));for (int i = 0; i < k; i++) {minHeap.add(nums[i]);}for (int i = 0; i < len; i++) {Integer topEle = minHeap.peek();//只要比堆顶大的元素，最顶弹出，遍历的元素进去if (nums[i] > topEle){minHeap.poll();minHeap.offer(nums[i]);}}return minHeap.peek();}