基于堆排序

  1. function swap(nums, x, y) {
  2.   var temp = nums[x];
  3.   nums[x] = nums[y];
  4.   nums[y] = temp;
  5. }
  7. function maxHeapify(nums, nonLeafNode, heapSize) {
  8.   var left = nonLeafNode * 2 + 1;
  9.   var right = nonLeafNode * 2 + 2;
  11.   var largest = nonLeafNode;
  13.   if (left < heapSize && nums[left] > nums[largest]) {
  14.     largest = left;
  15.   }
  16.   if (right < heapSize && nums[right] > nums[largest]) {
  17.     largest = right;
  18.   }
  20.   if (largest !== nonLeafNode) {
  21.     swap(nums, nonLeafNode, largest);
  22.     maxHeapify(nums, largest, heapSize);
  23.   }
  24. }
  26. function buildMaxHeap(nums, heapSize) {
  27.   for (var nonLeafNode = Math.floor(heapSize / 2) - 1; nonLeafNode >= 0; nonLeafNode--) {
  28.     maxHeapify(nums, nonLeafNode, heapSize);
  29.   }
  30. }
  32. function findKthLargest(nums, k) {
  33.   var heapSize = nums.length;
  34.   buildMaxHeap(nums, heapSize);
  36.   for (var i = nums.length - 1; i >= nums.length - k + 1; i--) {
  37.     swap(nums, 0, i);
  38.     maxHeapify(nums, 0, --heapSize);
  39.   }
  41.   return nums[0];
  42. }

总结

  • 原理：堆排序
  • 时间复杂度：O(nlogn)