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

题目描述

题目思路

• 看到第K个最大元素
• 那么直接使用最小堆

个人题解

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

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
class MinHeap {
    constructor() {
        this.heap = [];
    }

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

    getParentIndex(i) {
        return Math.floor((i - 1) / 2);
        // return (i-1) >> 1; // 老师用的是下面的,但是js位运算比mathAPi慢,所以...
    }

    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);
        }
    }

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

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

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

    shiftDown(index) {
        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);
        }

    }

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

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

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

}

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

    });
    return h.peek();
};
 console.log(findKthLargest([3,2,1,5,6,4],2));

时间复杂度（time complexity）

O(nlogk)

foreach是n

里面嵌套了一个insert()方法,是logk量级

空间复杂度（space complexity）

堆大小是k

O(K)