如何在 JavaScript 中找到数组中的前 K 大元素？

TOP K 问题是指在数组中找出最大或最小的 K 个元素。常见的解法有排序法、堆法和快速选择法，各有不同的时间复杂度和适用场景。以下从面试角度全面介绍这些方法：

1. 排序法（简单但高效度低）

• 思路：先将数组从大到小排序，然后取前 K 个元素获得最大 TOP K；或从小到大排序取前 K 个元素为最小 TOP K。
• 时间复杂度：O(n log n)，当使用高效排序算法（如快速排序）。
• 适用场景：小规模数组或数据量不大时。
• JavaScript 示例代码：

  function topKSort(arr, k) {
    // 降序排序取前k个 (最大TOP k)
    return arr.sort((a, b) => b - a).slice(0, k);
  }
    
  // 使用例子
  const arr = [3, 2, 3, 1, 2, 4, 5, 5, 6];
  console.log(topKSort(arr, 4)); // [6, 5, 5, 4]
  

2. 堆 / 优先级队列法（推荐面试回答）

• 思路：利用小顶堆 (min-heap) 求最大 TOP k，或大顶堆 (max-heap) 求最小 TOP k。
  • 具体步骤：
    1. 取前 K 个元素建堆（若小顶堆）。
    2. 遍历剩余元素，比较堆顶（小顶堆中最小）；若大于堆顶，弹出堆顶后插入当前元素。
    3. 遍历结束，堆中为结果。
• 时间复杂度：O(n log k)，比排序法更优。
• 适用场景：大规模数据，尤其在浏览器环境中可通过内置结构优化。
• 使用 JavaScript 的最小堆实现（优先级队列）： JavaScript 可直接使用优先队列（如 PriorityQueue from ‘priority_queue’）, 以下是简化的内部实现：

  class MinHeap {
    constructor() {
      this.heap = [];
    }
  
    size() {
      return this.heap.length;
    }
  
    isEmpty() {
      return this.size() === 0;
    }
  
    parent(index) {
      return Math.floor((index - 1) / 2);
    }
  
    left(index) {
      return 2 * index + 1;
    }
  
    right(index) {
      return 2 * index + 2;
    }
  
    swap(i, j) {
      [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }
  
    insert(val) {
      this.heap.push(val);
      this._shiftUp(this.size() - 1);
    }
  
    peek() {
      return this.heap;
    }
  
    extractMin() {
      const min = this.heap;
      this.swap(0, this.size() - 1);
      this.heap.pop();
      this._shiftDown(0);
      return min;
    }
  
    _shiftUp(index) {
      while (index > 0 && this.heap[index] < this.heap[this.parent(index)]) {
        this.swap(index, this.parent(index));
        index = this.parent(index);
      }
    }
  
    _shiftDown(index) {
      let left = this.left(index);
      let right = this.right(index);
      let minChild;
      while (left < this.size()) {
        minChild = left;
        if (right < this.size() && this.heap[right] < this.heap[left]) minChild = right;
        if (this.heap[index] > this.heap[minChild]) {
          this.swap(index, minChild);
          index = minChild;
          left = this.left(index);
          right = this.right(index);
        } else break;
      }
    }
  }
  
  function topKHeap(arr, k) {
    const heap = new MinHeap();
    // 建K个元素的堆（初始取前k个）
    for (let i = 0; i < k; i++) {
      heap.insert(arr[i]);
    }
    // 遍历剩余元素
    for (let i = k; i < arr.length; i++) {
      if (arr[i] > heap.peek()) { // 当前元素大于小顶堆顶时
        heap.extractMin();
        heap.insert(arr[i]);
      }
    }
    return heap.heap;
  }
  
  // 使用例子
  const heapExample = [3, 2, 3, 1, 2, 4, 5, 5, 6];
  console.log(topKHeap(heapExample, 4)); // [5, 5, 6, 4]，不保证顺序
  

3. 快速选择法（平均高效）

• 思路：基于快速排序划分函数分割出基准点，与 length - k 比较（求第 k 大元素），递归定位数据。
• 时间复杂度：平均为 O(n)，最差 O(n^2)。
• 适用场景：只需求单个 K值或内存受限时。
• JavaScript 示例代码：

  function quickSelect(arr, k) {
    const partition = (arr, left, right) => {
      const pivot = arr[left];
      let i = left;
      for (let j = i + 1; j <= right; j++) {
        if (arr[j] < pivot) {
          i++;
          [arr[i], arr[j]] = [arr[j], arr[i]];
        }
      }
      [arr[left], arr[i]] = [arr[i], arr[left]];
      return i;
    };
  
    const select = (arr, left, right, k) => {
      if (left === right) return arr[left];
      const pivotIndex = partition(arr, left, right);
      if (k === pivotIndex) return arr[pivotIndex];
      return pivotIndex > k ? select(arr, left, pivotIndex - 1, k) : select(arr, pivotIndex + 1, right, k);
    };
  
    return select(arr, 0, arr.length - 1, arr.length - k);
  }
  
  // 使用例子：求第k大的元素（第4大元素为4）
  const quickArr = [3, 2, 3, 1, 2, 4, 5, 5, 6];
  console.log(quickSelect(quickArr, 4)); // 4
  

综合建议

• 面试中优先推荐堆法：时间复杂度优且易于实现。
• 海量数据：使用分区减数据或混合策略优化性能（如内存使用）。
• 性能对比：小型数组用排序简捷，大型用堆或快速选择。根据实际场景 (如重复元素和内存) 做优化能突出算法知识深度。