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前面
            @Override
            public 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++) {//大小为k
            minHeap[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;
    }
}