词频统计

Question

在面试前，我面临这样一个问题：

\n\n

给定一个由单个空格分隔的单词组成的字符串，按单词在字符串中出现的次数降序打印单词。

\n\n

例如，输入字符串 \xe2\x80\x9ca bb\xe2\x80\x9d 将生成以下输出：

\n\n

b : 2\na : 1\n

\n\n

首先，我想说输入字符串是由单字母单词还是由多字母单词组成还不太清楚。如果是前者，事情可能会很简单。

\n\n

这是我的想法：

\n\n

int c[26] = {0};\nchar *pIn = strIn;\n\nwhile (*pIn != 0 && *pIn != ' ')\n{\n    ++c[*pIn];\n    ++pIn;\n}\n\n/* how to sort the array c[26] and remember the original index? */\n

\n\n

我可以获得输入字符串中每个单字母单词的频率统计信息，并且可以对其进行排序（使用 QuickSort 或其他方式）。但是在计数数组排序后，如何获取与计数相关的单字母单词，以便稍后将它们成对打印出来？

\n\n

如果输入字符串由多字母单词组成，我计划使用 amap<const char *, int>来跟踪频率。但同样，如何对映射的键值对进行排序？

\n\n

问题是用 C 或 C++ 编写的，欢迎提出任何建议。

\n\n

谢谢！

\n

Answer 1

我会使用 astd::map<std::string, int>来存储单词及其计数。然后我会用这样的东西来得到这些词：

while(std::cin >> word) {
    // increment map's count for that word
}

最后，您只需要弄清楚如何按频率顺序打印它们，我将其作为练习留给您。