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

sisterAn/JavaScript-Algorithms#60

代码

var findKthLargest = function(nums, k) {
  // return nums.sort((a, b) =>  b - a)[k -1]
  let heap = [], i = 0;
  // 从数组中取出k个数构建一个小顶堆
  while(i < k) {
    heap.push(nums[i++]);
  }
  buildHeap(heap, k);
  // 从k位开始遍历数组
  for(let i = k; i < nums.length; i++) {
    if (heap[0] < nums[i]) {
      // 替换并堆化
      heap[0] = nums[i];
      heapify(heap, k , 0);
    }
  }
  // 返回堆顶元素
  return heap[0];
};

// 原地建立小顶堆
function buildHeap(heap, k) {
  if (k === 0) return;
  for(let i = k >> 1; i >= 0; i--) {
    heapify(heap, k, i)
  }
}

// 堆化
function heapify(heap, k, i) {
  // 自上而下堆化
  while(true) {
    let minIndex = i;
    if ((i << 1) <= k && heap[i << 1] < heap[i]) {
      minIndex = i << 1;
    }
    if ((i << 1) + 1 <= k && heap[(i << 1) + 1] < heap[minIndex]) {
      minIndex = (i << 1) + 1;
    }
    if (minIndex !== i) {
      swap(heap, minIndex, i);
      i = minIndex;
    } else {
      break;
    }
  }
}

// 交换
function swap(heap, minIndex, i) {
  let temp = heap[i];
  heap[i] = heap[minIndex];
  heap[minIndex] = temp;
}

复杂度分析

时间复杂度 $O(NlogK)$

空间复杂度 $O(K)$