215. 数组中的第K个最大元素

[swiftwind0405]

方法一：最小堆

解题思想：

• 构建一个最小堆，并依次把数组的值插入堆中
• 当堆的容量超过 K，就删除堆顶
• 插入结束后，堆顶就是第K个最大的元素

代码：
最小堆的类：

class MinHeap {
    constructor() {
        this.heap = [];
    }

    getParentIndex(i) {
        return (i - 1) >> 1;
    }
    
    getLeftIndex(i) {
        return 2 * i + 1;
    }

    getRightIndex(i) {
        return 2 * i + 2;
    }

    swap(i1, i2) {
        const temp = this.heap[i1];
        this.heap[i1] = this.heap[i2];
        this.heap[i2] = temp;
    }

    shiftUp(index) {
        if ( index === 0) return;
        const parentIndex = this.getParentIndex(index);
        if (this.heap[parentIndex] > this.heap[index]) {
            this.swap(parentIndex, index);
            this.shiftUp(parentIndex);
        }
    }

    shiftDown(index) {
        if (index > this.heap.length - 1) return;
        const leftIndex = this.getLeftIndex(index);
        const rightIndex = this.getRightIndex(index);
        if (this.heap[leftIndex] < this.heap[index]) {
            this.swap(leftIndex, index);
            this.shiftDown(leftIndex);
        }
        if (this.heap[rightIndex] < this.heap[index]) {
            this.swap(rightIndex, index);
            this.shiftDown(rightIndex);
        }
    }

    insert(value) {
        this.heap.push(value);
        this.shiftUp(this.heap.length - 1);
    }

    pop() {
        this.heap[0] = this.heap.pop();
        this.shiftDown(0)
    }

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

    size() {
        return this.heap.length;
    }
}

var findKthLargest = function(nums, k) {
    const h = new MinHeap();
    nums.forEach(num => {
        h.insert(num);
        if (h.size() > k) {
            h.pop();
        }
    });
    return h.peek();
};

复杂度分析：

• 时间复杂度：O(n*logK)，遍历nums中的insert与pop的时间复杂度最大都是logK；
• 空间复杂度：O(K)，K是堆的大小。