使用哈希表和最小堆找到数组中前 K 个高频元素 - JavaScript 实现

要找到数组中前 K 个高频元素，可以使用哈希表和最小堆（Min-Heap）结合的方法。以下是详细的步骤和代码实现：

1. 使用哈希表统计元素频率

首先，我们遍历数组，使用哈希表（JavaScript 中的 Map）来统计每个元素出现的频率。

2. 使用最小堆维护前 K 个高频元素

接下来，我们使用最小堆来维护前 K 个高频元素。最小堆的特点是堆顶元素是堆中最小的元素，这样我们可以很容易地替换掉堆顶元素，从而保持堆中始终是前 K 个高频元素。

3. 实现代码

以下是使用 JavaScript 实现的代码：

class MinHeap {
    constructor() {
        this.heap = [];
    }

    push(val) {
        this.heap.push(val);
        this.bubbleUp(this.heap.length - 1);
    }

    pop() {
        const min = this.heap[0];
        const end = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.bubbleDown(0);
        }
        return min;
    }

    bubbleUp(index) {
        const element = this.heap[index];
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            const parent = this.heap[parentIndex];
            if (element[1] >= parent[1]) break;
            this.heap[index] = parent;
            index = parentIndex;
        }
        this.heap[index] = element;
    }

    bubbleDown(index) {
        const length = this.heap.length;
        const element = this.heap[index];
        while (true) {
            let leftChildIndex = 2 * index + 1;
            let rightChildIndex = 2 * index + 2;
            let swap = null;
            let leftChild, rightChild;

            if (leftChildIndex < length) {
                leftChild = this.heap[leftChildIndex];
                if (leftChild[1] < element[1]) {
                    swap = leftChildIndex;
                }
            }

            if (rightChildIndex < length) {
                rightChild = this.heap[rightChildIndex];
                if (
                    (swap === null && rightChild[1] < element[1]) ||
                    (swap !== null && rightChild[1] < leftChild[1])
                ) {
                    swap = rightChildIndex;
                }
            }

            if (swap === null) break;
            this.heap[index] = this.heap[swap];
            index = swap;
        }
        this.heap[index] = element;
    }

    size() {
        return this.heap.length;
    }

    peek() {
        return this.heap[0];
    }
}

function topKFrequent(nums, k) {
    const frequencyMap = new Map();
    for (const num of nums) {
        frequencyMap.set(num, (frequencyMap.get(num) || 0) + 1);
    }

    const minHeap = new MinHeap();
    for (const [num, freq] of frequencyMap.entries()) {
        if (minHeap.size() < k) {
            minHeap.push([num, freq]);
        } else if (freq > minHeap.peek()[1]) {
            minHeap.pop();
            minHeap.push([num, freq]);
        }
    }

    const result = [];
    while (minHeap.size() > 0) {
        result.push(minHeap.pop()[0]);
    }

    return result.reverse();
}

// 示例用法
const nums = [1, 1, 1, 2, 2, 3];
const k = 2;
console.log(topKFrequent(nums, k)); // 输出: [1, 2]

4. 代码解释

• MinHeap 类：实现了一个最小堆，用于维护前 K 个高频元素。
• topKFrequent 函数：
  • 首先使用 Map 统计每个元素的频率。
  • 然后使用最小堆来维护前 K 个高频元素。
  • 最后将堆中的元素取出并返回。

5. 时间复杂度

• 统计频率的时间复杂度为 O(N)，其中 N 是数组的长度。
• 维护最小堆的时间复杂度为 O(N log K)，因为每次插入和删除操作的时间复杂度为 O(log K)。
• 总体时间复杂度为 O(N log K)。

6. 空间复杂度

• 哈希表和最小堆的空间复杂度为 O(N)。

这种方法在大多数情况下都能高效地找到前 K 个高频元素。