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的堆就可以了。