高效统计文本中前K个高频单词 -

题目

高效统计文本中前K个高频单词

信息

类型：问答
难度：⭐⭐

考点

STL容器选择,迭代器应用,算法性能优化,自定义排序

快速回答

实现步骤：

使用unordered_map统计单词频率（O(1)平均插入）
将键值对转移到vector中处理
自定义比较函数按频率降序排序
使用partial_sort优化性能（O(n log k)）
处理边界条件（空输入/k值过大）

## 解析

问题描述

实现函数vector<pair<string, int>> topKFrequent(const string& text, int k)，统计文本中单词频率，返回前k个高频单词及其频率。要求：

区分大小写（"Apple"和"apple"不同）
单词由空格分隔，过滤标点符号
时间复杂度优于O(n log n)

原理说明

核心优化点：

容器选择：unordered_map哈希表实现O(1)平均插入，优于map的O(log n)
部分排序：partial_sort仅排序前k个元素（O(n log k)），优于sort的O(n log n)
内存管理：转移数据到vector避免直接操作map迭代器

代码示例

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <sstream>
#include <cctype>

using namespace std;

vector<pair<string, int>> topKFrequent(const string& text, int k) {
    if (text.empty() || k <= 0) return {};

    // 1. 频率统计（过滤非字母字符）
    unordered_map<string, int> freqMap;
    stringstream ss(text);
    string word;
    while (ss >> word) {
        // 移除非字母字符
        word.erase(remove_if(word.begin(), word.end(), 
                   [](char c) { return !isalpha(c); }), word.end());
        if (!word.empty()) freqMap[word]++;
    }

    // 2. 转移数据到vector
    vector<pair<string, int>> items(freqMap.begin(), freqMap.end());

    // 3. 部分排序优化
    k = min(k, static_cast<int>(items.size()));
    partial_sort(items.begin(), items.begin() + k, items.end(),
        [](const auto& a, const auto& b) {
            return a.second > b.second;  // 按频率降序
        });

    // 4. 返回前k个元素
    return vector<pair<string, int>>(items.begin(), items.begin() + k);
}

// 测试用例
int main() {
    string text = "Apple apple Banana. banana; Cherry cherry apple";
    auto result = topKFrequent(text, 2);
    for (const auto& p : result) {
        cout << p.first << ": " << p.second << endl;
    }
    /* 输出：
       apple: 2
       Apple: 1   （区分大小写） */
    return 0;
}

最佳实践

性能优化：当k远小于元素总量时，partial_sort比完全排序快10倍以上
内存优化：大文本场景可用reserve()预分配map/vector内存
健壮性：处理空单词、非法k值等边界条件

常见错误

错误1：直接对unordered_map迭代器排序（需转移到线性容器）
错误2：使用map导致O(n log n)插入性能损失
错误3：未处理标点导致"word,"和"word"被识别为不同单词
错误4：完全排序所有元素造成不必要性能开销

扩展知识

替代方案：可用priority_queue（最小堆）实现O(n log k)：

priority_queue<pair<int, string>> pq;
for (auto& item : freqMap) {
    pq.push({-item.second, item.first}); // 负值实现最小堆
    if (pq.size() > k) pq.pop();
}