215. [✔][M]数组中的第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

提示：

• 1 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

---

题解：

手写heap

// @lc code=start
function findKthLargest(nums: number[], k: number): number {
    class Heap {
        data: number[];
        comparator: (a: number, b: number) => boolean;

        constructor(data: number[] = [], comparator: (a: number, b: number) => boolean = (a: number, b: number) => (a > b)) {
            this.data = data;
            this.comparator = comparator;
            this.heapify();
        }

        get size() {
            return this.data.length;
        }

        heapify() {
            for (let i = Math.floor(this.size / 2 - 1); i >= 0; i--) {
                this.down(i);
            }
        }

        swap(l: number, r: number) {
            [this.data[l], this.data[r]] = [this.data[r], this.data[l]];
        }

        down(index: number) {
            let lastIndex = this.size - 1;

            while (true) {
                let findIndex = index;
                let leftIndex = index * 2 + 1;
                let rightIndex = index * 2 + 2;

                if (leftIndex <= lastIndex && this.comparator(this.data[leftIndex], this.data[findIndex])) {
                    findIndex = leftIndex;
                }
                if (rightIndex <= lastIndex && this.comparator(this.data[rightIndex], this.data[findIndex])) {
                    findIndex = rightIndex;
                }
                if (findIndex !== index) {
                    this.swap(findIndex, index);
                    index = findIndex;
                } else {
                    break;
                }
            }
        }

        up(index: number) {
            while (index > 0) {
                let parentIndex = (index - 1) >> 1
                if (this.comparator(index, parentIndex)) {
                    this.swap(index, parentIndex);
                    index = parentIndex;
                } else {
                    break;
                }
            }
        }

        push(val: number) {
            this.data.push(val);
            this.up(this.size - 1);
        }

        pop() {
            if (this.size === 0) {
                return null;
            }
            this.swap(0, this.size - 1);
            let curr = this.data.pop();
            this.down(0);
            return curr;
        }

        peek() {
            return this.data[0];
        }
    }

    let heap = new Heap(nums, (a, b) => a > b);

    let res;

    for (let i = 0; i < k; i++) {
        res = heap.pop();
    }

    return res;

};
// @lc code=end