BFE.devAI解答 - JavaScript 代码题
152. 找到最大的前k个元素

一种解法是使用快速排序的思想，每次确定一个数的位置，然后判断这个位置是否在前k个位置内，不在则递归排序左边或右边的部分。

function topK(nums, k) {
  if (k >= nums.length) {
    return nums;
  }
  return quickSort(nums, 0, nums.length - 1, k);
}

function quickSort(nums, left, right, k) {
  if (left >= right) {
    return nums.slice(0, k);
  }
  let pivot = nums[left];
  let i = left;
  let j = right;
  while (i < j) {
    while (i < j && nums[j] <= pivot) {
      j--;
    }
    nums[i] = nums[j];
    while (i < j && nums[i] >= pivot) {
      i++;
    }
    nums[j] = nums[i];
  }
  nums[i] = pivot;
  if (i >= k) {
    return quickSort(nums, left, i - 1, k);
  } else {
    return quickSort(nums, i + 1, right, k);
  }
}

时间复杂度是O(nlogn)，空间复杂度是O(logn)。

还有一种解法是使用堆排序的思想。先将前k个元素建立小根堆，然后遍历数组剩余部分，若当前元素大于堆顶元素，则将其插入堆中，并将堆顶元素弹出。最后返回堆中的元素即为前k个最大元素。

function topK(nums, k) {
  let heap = [];
  for (let i = 0; i < k; i++) {
    heap.push(nums[i]);
  }
  buildHeap(heap);
  for (let i = k; i < nums.length; i++) {
    if (nums[i] > heap[0]) {
      heap[0] = nums[i];
      heapify(heap, 0);
    }
  }
  return heap;
}

function buildHeap(nums) {
  for (let i = Math.floor(nums.length / 2); i >= 0; i--) {
    heapify(nums, i);
  }
}

function heapify(nums, idx) {
  let smallest = idx;
  let left = idx * 2 + 1;
  let right = idx * 2 + 2;
  if (left < nums.length && nums[left] < nums[smallest]) {
    smallest = left;
  }
  if (right < nums.length && nums[right] < nums[smallest]) {
    smallest = right;
  }
  if (smallest !== idx) {
    [nums[idx], nums[smallest]] = [nums[smallest], nums[idx]];
    heapify(nums, smallest);
  }
}

时间复杂度是O(nlogk)，空间复杂度是O(k)。堆排序的优点是可以处理数据量很大的情况，只需要维护一个大小为k的堆就可以了。