java数据结构与算法刷题-----LeetCode215. 数组中的第K个最大元素

java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：https://blog.csdn.net/grd_java/article/details/123063846

解题思路：时间复杂度O($n$)，空间复杂度O($lo{g}_{2}n$)

1. 使用小根堆，建堆时间复杂度O(k),调整堆(删除堆顶并插入新元素)O($n\ast lo{g}_{2}k$),其中k是题目要求的返回第k最大元素。因此小根堆大小为k，故建堆为O(k). 共计O($k+n\ast lo{g}_{2}k$) = O(n)
2. 不断地将元素插入到小根堆（根最小，其它元素都比根大）中，当堆中有k个元素，此时还需要往堆中插入元素时，需要进行判断。
3. 因为此时堆顶元素正好是堆中倒数第k大元素。如果新插入元素比堆顶大。证明当前堆顶不是倒数第k大
4. 则堆顶删除，并将新元素插入。此时调整堆，新的堆顶元素为第k大。以此类推。直到所有元素入堆后。
5. 最终返回堆顶即可。

堆排序https://blog.csdn.net/grd_java/article/details/136937525

代码:当前官方增加了很多测试用例，已经无法超越100%的用户了，目前最快的算法，只能达到17ms，进行优化后，也只到了15ms。我查看2021年提交时的记录，是3ms超越100%。目前已经无法达到了。

1. 使用Java提供的优先级队列实现小根堆（面试时候肯定不让你用。因此这个代码帮你理解整体的思路。然后第二个实现方法，我们需要自己实现小根堆）
   

class Solution {//[6,5]//public int findKthLargest(int[] nums, int k) {PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {//返回值>0,o1放在o2后面。反之o1放o2前面//小根堆，小的在前面。利用o1-o2实现。如果o1小，o1-o2<0，o1会放在o2前面//如果o1大o2小，o1-o2>0,o1会放在o2后面。而小的o2放在o1前面@Overridepublic int compare(Integer o1, Integer o2) {return o1 - o2;}});for(int num:nums){if(queue.size() == k){if(queue.peek() < num) {queue.poll();queue.offer(num);}}else{queue.offer(num);}}return queue.poll();}
}

2. 自己实现小根堆，因为Java自带容器加了很多健壮性和线程安全的逻辑，所以效率较慢，我们自己实现小根堆就会快很多。
   

class Solution {public int findKthLargest(int[] nums, int k) {int[] minHeap = new int[k];//小根堆for (int i = 0; i < k; i++) {//大小为kminHeap[i] = nums[i];}//k/2-1是二叉树的知识，代表以k个结点构成的二叉树的第一个非叶子结点。k/2-2是第二个非叶子，以此类推。i == 0是整个二叉树的根结点for (int i = k / 2 - 1; i >= 0; i--) {//调整小根堆，从下到上，依次让每一颗子树满足小根堆adjustHeap(minHeap, i);//i是二叉树的每个非叶子结点，小根堆的要求是：每个子树，根结点都是整棵树最小}//小根堆构建完成后，minHeap[0]就是当前第k大的数。接下来需要不断进行判断和入堆操作for (int i = k; i < nums.length; i++) {if (nums[i] > minHeap[0]) {//如果当前i，是比小根堆堆顶更大的元素，那么堆顶不是第k大，minHeap[0] = nums[i];//将堆顶出堆，并将i放在堆顶位置adjustHeap(minHeap, 0);//此时很有可能小根堆逻辑被破坏，也就是i太大，不满足小根堆，因此需要让i进行下降调整，让其重新满足小根堆定义}}return minHeap[0];}/*** 以root为根结点构建/调整堆* @param array 堆* @param root 当前根结点*/private void adjustHeap(int[] array, int root) {//让root结点下降到合适位置，以满足小根堆效果（任何一颗子树，根结点都是最小的）while (true) {//当堆调整完成后，结束int left = 2 * root + 1;//获得root的左子结点下标int right = left + 1;//获得root的右子结点下标int min = root;//最小值，最终需要放到root结点位置//如果左子结点存在，并且左子结点更小，让min指向这个结点if (left < array.length && array[left] < array[min]) min = left;//如果右子结点存在，并且右子结点更小，让min指向这个结点if (right < array.length && array[right] < array[min]) min = right;//如果min == root说明小根堆调整结束if (min == root) break;//让min当前指向位置和root交换，也就是下降操作，说明root当前指向的结点不是最小值，不满足小根堆//因为小根堆，越上面层次的结点，越小，所以如果当前root太大，需要让其下降swap(array, root, min);//root本次下降完成后，min的位置是root新的位置。因为root下降到min的位置//让root指向min，然后继续循环，判断是否root需要继续下降。直到它下降到合适位置root = min;}}private void swap(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}
}