【LeetCode热题100】【堆】数组中的第K个最大元素

题目链接：215. 数组中的第K个最大元素 - 力扣（LeetCode）

快速选择

快速排序的思想是每次将数列分成一边大一边小的继续递归下去，平均复杂度是O(nlogn)，快速选择思路基本一样，不同的是只需要找一边继续递归下去，本来快速排序的递归树到快速选择只需要递归树里面的一支分支，平均复杂度是O(nlogn)，理论上是好的，但是实测不一定好

class Solution {
    int QC(vector<int> &nums, int k, int low, int high) {
        if (low == high)
            return nums[k];
        int pivot = nums[low], i = low, j = high;
        while (i < j) {
            while (i < j && nums[j] <= pivot)j--; // 右边找到大的
            while (i < j && nums[i] >= pivot)i++; // 左边找到小的
            if (i < j)
                std::swap(nums[i], nums[j]); // 大的放左边，小的放右边
        }
        nums[low]=nums[i]; // 腾位置给枢纽元素
        nums[i]=pivot;
        if (k <= i)
            return QC(nums, k, low, i);
        return QC(nums, k, j + 1, high);
    }

public:
    int findKthLargest(vector<int> &nums, int k) {
        return QC(nums, k-1, 0, nums.size() - 1);
    }
};

堆排序

手写一个堆，一个k容量的小顶堆，遍历一次数列，如果有比堆顶元素大的更新堆顶，重新调整堆，这样下来堆里就是最大的k个数，堆顶就是第k大的

堆主要就是调整堆如何实现，直接以原数组为容器承载，递归调整堆

class Solution {
public:
    void adjustMinHeap(vector<int> &nums, int root, int heapSize) {
        int left = 2 * root + 1;
        int right = left + 1;
        int next = root; // 找到比根节点小的
        if (left < heapSize && nums[left] < nums[next])
            next = left;
        if (right < heapSize && nums[right] < nums[next])
            next = right;
        if (next != root) {
            std::swap(nums[next], nums[root]);
            adjustMinHeap(nums, next, heapSize);
        }
    }

    void buildMinHeap(vector<int> &nums, int heapSize) {
        for (int i = heapSize / 2 - 1; i >= 0; i--)
            adjustMinHeap(nums, i, heapSize);
    }

    int findKthLargest(vector<int> &nums, int k) {
        buildMinHeap(nums, k);
        for (int i = k; i < nums.size(); i++) {
            if (nums[i] > nums[0]) {
                std::swap(nums[i], nums[0]);
                adjustMinHeap(nums, 0, k);
            }
        }
        return nums[0];
    }
};