leetcode热题HOT 215. 数组中的第K个最大元素(堆和快速排序)

一、问题描述：

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

二、基于堆排序的选择方法：建立一个大根堆，堆顶元素nums[0]为最大值，做 k−1次删除操作后的堆顶元素就是数组中第 k 个最大的元素。

1、堆是什么？

堆是一种特殊的完全二叉树，具有堆化的特性，可以用数组实现。与一般的排序方式所定义的有序不同，看似堆数组中的数字并未按照升序或降序排列，但其实这棵树是有序的状态。按照元素升序和降序排序分为大根堆和小根堆。
大根堆: 父结点的值大于或等于其子结点的值。
小根堆: 父结点的值小于或等于其子结点的值。
与二叉树类似，堆能以 O(logN) 的时间复杂度完成插入、删除和查找操作，通过调整数组中元素的顺序，维护堆的结构。

2、构建大根堆

在最大堆中，每个节点的值都大于或等于其子节点的值。由于叶子节点没有子节点，它们已经满足了这个性质，因此不需要进行任何调整。而最后一个非叶子节点的索引是数组长度的一半减一。因此，从数组长度的一半 n / 2 向前遍历，可以确保每个非叶子节点都能被正确处理。

    public void buildMaxHeap(int[] a, int n) {
        //从数组长度的一半处向前遍历，可以确保每个非叶子节点都能被正确处理。
        for(int i = n / 2; i >= 0; --i) {
            maxHeapify(a, i, n);
        }
    }

3、调整大根堆

从最后一个非叶子节点开始向前遍历，比较自己与左右子结点的大小，如果小于子结点就交换（即：下调）。下调之后继续与新的左右孩子结点进行比较，能够下调就下调，直到不能下调为止。向前继续移动，直到所有结点均遍历一遍，所有父结点均大于其孩子结点，便成为了一棵大根堆。

    //和左右子节点比较，若大于子节点，向下调
    public void maxHeapify(int[] a, int i, int n) {
        int l = i * 2 + 1, r = i * 2 + 2, max = i;
        if (l < n && a[l] > a[max]) {
            max = l;
        }
        if (r < n && a[r] > a[max]) {
            max = r;
        }
        if (max != i) {
            swap(a, i, max);
            maxHeapify(a, max, n);//递归调用，直到满足根节点大于左右节点的值
        }
    }

4、删除操作

我们要找到第K大的元素，那么需要从堆中删除K次最大元素nums[0]。每次将堆顶元素与最后一个元素进行交换，这样最大值就来到了数组的最后。由于堆顶发生了变化，可能不再是一个大根堆，因此需要对大根堆进行调整。

        for(int i = nums.length - 1; i >= nums.length - k + 1; --i) {
            swap(nums, 0, i);//堆顶元素与数组最后一位元素交换
            --n;//长度减一
            maxHeapify(nums, 0, n);//删除堆顶元素，无序的部分被放到末尾
        }

5、完整代码：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        //数组中的第K个最大元素就是第n - k大的元素，对应排序后的数组的第n - k个元素
        buildMaxHeap(nums, n);
        for(int i = nums.length - 1; i >= nums.length - k + 1; --i) {
            swap(nums, 0, i);//堆顶元素与数组最后一位元素交换
            --n;//长度减一
            maxHeapify(nums, 0, n);//删除堆顶元素，无序的部分被放到末尾
        }
        return nums[0];//删除K次，返回堆顶元素，即为我们要找的值
    }  
    public void buildMaxHeap(int[] a, int n) {
        //从数组长度的一半处向前遍历，可以确保每个非叶子节点都能被正确处理。
        for(int i = n / 2; i >= 0; --i) {
            maxHeapify(a, i, n);
        }
    }
    //和左右子节点比较，若大于子节点，向下调
    public void maxHeapify(int[] a, int i, int n) {
        int l = i * 2 + 1, r = i * 2 + 2, max = i;
        if (l < n && a[l] > a[max]) {
            max = l;
        }
        if (r < n && a[r] > a[max]) {
            max = r;
        }
        if (max != i) {
            swap(a, i, max);
            maxHeapify(a, max, n);//递归调用，直到满足根节点大于左右节点的值
        }
    }
    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

时间复杂度分析：总体而言，这段代码使用了堆排序的思想，在构建最大堆后，通过反复交换堆顶元素和末尾元素，并对堆进行调整，最终得到第 k 个最大的元素。时间复杂度为 O(nlogn)，空间复杂度为 O(1)。

三、基于快速排序的选择方法：先对原数组升序排序，再返回倒数第 k个位置。

快速排序是一种常用的排序算法，其基本思想是通过选取一个基准值，将数组分割成两部分，一部分小于基准值，另一部分大于基准值，然后对这两部分分别进行递归排序。具体步骤如下：

选择一个基准值（通常是数组的第一个元素）。
将数组中小于基准值的元素移到基准值的左边，大于基准值的元素移到基准值的右边。
继续对基准值左右两部分分别递归进行快速排序。
这是一个递归过程，直到每个子数组的大小为 1 或 0 时，排序完成。

代码示例：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        // 数组中的第 k 个最大元素就是第 n - k 大的元素，对应排序后的数组的第 n - k 个元素
        return quickselect(nums, 0, n - 1, n - k);
    }
    
    // 快速选择算法
    int quickselect(int[] nums, int l, int r, int k) {
        // 如果左右指针相遇，说明排序完成
        if (l == r) return nums[k];
        
        // 以 nums[l] 为基准，将数组中小于基准值的元素移到基准值的左边，大于基准值的元素移到基准值的右边
        int x = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            i++; while (nums[i] < x) i++;  // 找到第一个大于等于基准值的元素
            j--; while (nums[j] > x) j--;  // 找到第一个小于等于基准值的元素
            // 如果 i < j，交换这两个元素
            if (i < j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        
        // 根据 j 的位置确定下一步递归的范围
        if (k <= j) return quickselect(nums, l, j, k);  // 第 k 个最大的元素在左边部分
        else return quickselect(nums, j + 1, r, k);     // 第 k 个最大的元素在右边部分
    }  
}