41、数组中的第K个最大元素(借助堆实现)

总体思路:

我们可以从数组中取出 k 个元素构造一个小顶堆,然后将其余元素与小顶堆对比,如果大于堆顶则替换堆顶,然后堆化,所有元素遍历完成后,堆中的堆顶即为第 k 个最大值。

步骤:

  1. 从数组中取前 k 个数( 0 到 k-1 位),构造一个小顶堆
  2. 从 k 位开始遍历数组,每一个数据都和小顶堆的堆顶元素进行比较,如果小于堆顶元素,则不做任何处理,继续遍历下一元素;如果大于堆顶元素,则将这个元素替换掉堆顶元素,然后再堆化成一个小顶堆。
  3. 遍历完成后,堆顶的数据就是第 K 大的数据。含有k个元素的小根堆就是前k大的元素。

时间复杂度:遍历数组需要 O(n) 的时间复杂度,一次堆化需要 O(logk) 时间复杂度,所以利用堆求 Top k 问题的时间复杂度为 O(nlogk)
空间复杂度:O(k)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    let heap = [,]; //heap[0]为空,为了从下标1开始计算
    for(let i=0;i<k;i++){ // 堆heap中存放k个元素,便于创建k个元素的小根堆
        heap.push(nums[i])
    }
    buildHeap(heap,k);

    // 从第k+1个元素开始,与小根堆的根节点(即最小节点)比较
    //   若比小根堆的根节点大,则替换根节点,重新调整
    //   最后保证k个节点的小根堆中,存放的是最大的前k个元素
    for(let i=k;i<nums.length;i++){
        if(nums[i]>heap[1]){
            heap[1] = nums[i]; //替换根节点
            heapify(heap,k,1); //调整为小根堆。从堆的第1个节点开始调整
        }
    }
    return heap[1]; //此时heap数组中,存放是前k大元素
};

//1. 建立k个元素的小根堆。注意:heap数组从1开始计数
function buildHeap(heap,k){
    if(k===1) return;
    // 依次调整每个非叶结点(与其左右孩子比较),并调整因交换所影响的子节点
    for(let i=Math.floor(k/2);i>=1;i--){ //从最后一个非叶结点开始调整
        heapify(heap,k,i);
    }
} 

//2. 调整节点i及其子孙结点 为小根堆。 注意:小根堆大小为k,避免越界
function heapify(heap,k,i){
    while(true){
        let minIndex = i; //记录交换的节点。交换后,再对交换的节点进行调整
        if(i*2<=k && heap[i]>heap[i*2]){ 
        minIndex = i*2;
        }
        if(i*2+1 <= k && heap[minIndex]>heap[i*2+1]){
            minIndex = i*2+1;
        }
        if(minIndex !== i){ //存在其左右孩子比其小
            let temp = heap[i];
            heap[i] = heap[minIndex];
            heap[minIndex] = temp;
            i = minIndex; //将交换的节点改为当前要调整的根节点(避免i节点调整后,影响其它节点)
        } else{ //当前节点i,及其交换的节点 都已调整完毕,退出
            break;
        }
        }
}

上一篇:ABC 214 G,H 题解


下一篇:A*算法解决8数码问题