5

在面试前，我遇到了这样一个问题：

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

例如，“abb”的输入字符串将生成以下输出：

b : 2
a : 1

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

这是我的想法：

int c[26] = {0};
char *pIn = strIn;

while (*pIn != 0 && *pIn != ' ')
{
    ++c[*pIn];
    ++pIn;
}

/* how to sort the array c[26] and remember the original index? */

我可以获得输入字符串中每个单字母单词的频率统计数据，并且可以对其进行排序（使用 QuickSort 或其他）。但是count数组排序后，如何获取与count关联的单字母单词，以便以后成对打印出来呢？

如果输入字符串由多个字母组成，我打算使用 amap<const char *, int>来跟踪频率。但同样，如何对地图的键值对进行排序？

问题在 C 或 C++ 中，欢迎提出任何建议。

谢谢！

4

4 回答 4

2

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

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

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

于 2011-12-30T15:54:06.883 回答
1

以 C 语言为例：

我喜欢蛮力、直接的算法，所以我会这样做：

  1. 标记输入字符串以给出未排序的单词数组。实际上，我必须实际移动每个单词（因为每个单词的长度都是可变的）；我想我需要一个 char* 数组，我将把它用作 qsort() 的 arg。

  2. qsort( ) （降序）那个单词数组。（在 qsort() 的 COMPAR 函数中，假设较大的单词是较小的单词，以便数组获得降序排序。）

3.a. 遍历现在排序的数组，寻找相同单词的子数组。一个子数组的结束和下一个数组的开始，由我看到的第一个不相同的单词表示。3.b。当我到达子数组的末尾（或排序数组的末尾）时，我知道（1）单词和（2）子数组中相同单词的数量。

编辑新步骤 4：在另一个数组（称为 array2）中保存一个 char* 到子数组中的一个单词以及子数组中相同单词的计数。

  1. 当排序数组中没有更多单词时，我就完成了。是时候打印了。

  2. qsort( ) array2 按词频。

  3. 通过array2，打印每个单词及其频率。

我受够了！我们去吃午饭吧。

于 2011-12-30T16:05:04.390 回答
1

假设您只需要 26 个选项肯定是错误的，因为您的雇主也希望允许使用多字符单词（甚至可能是数字？）。

这意味着您将需要一个可变长度的数组。我强烈建议使用矢量，甚至更好的是地图。

要查找字符串中的字符序列，请查找您的当前位置（从 0 开始）和下一个空格的位置。然后就是这个词。将当前位置设置为空格，然后再做一次。不断重复这个直到你结束。

通过使用地图，您已经有了可用的字数/计数。

如果您申请的工作需要大学技能，我强烈建议您通过添加某种散列函数来优化地图。但是，从问题的难度来看，我认为情况并非如此。

于 2011-12-30T15:56:53.563 回答
1

我之前的所有答案都没有给出真正的答案。

让我们考虑一个潜在的解决方案。

有一种或多或少的标准方法来计算容器中的东西。

我们可以使用关联容器，例如 astd::map或 a std::unordered_map。在这里，我们将一个“键”（在这种情况下是单词）与一个值关联起来，在这种情况下是特定单词的计数。

幸运的是，这些地图有一个非常好的索引operator[]。这将查找给定的键，如果找到，则返回对该值的引用。如果未找到，则它将使用密钥创建一个新条目并返回对新条目的引用。因此，在这两种情况下，我们都会获得对用于计数的值的引用。然后我们可以简单地写：

std::unordered_map<char,int> counter{};
counter[word]++;

这看起来非常直观。

完成此操作后，您已经有了频率表。要么按键（单词）排序，要么使用 astd::map或未排序，但使用 a 可以更快地访问std::unordered_map。

现在您要根据频率/计数进行排序。不幸的是，这在地图上是不可能的。

因此，我们需要使用第二个容器，例如 ```std::vector`````，然后我们可以对std::sort任何给定的谓词进行排序，或者，我们可以将值复制到容器中，例如std::multiset隐含排序的它的元素。

为了取出 a 的单词，std::string我们只需使用 astd::istringstream和标准提取运算符>>。没什么大不了的。

而且因为为 std 容器编写了所有这些长名称，所以我们使用using关键字创建别名。

毕竟，我们现在编写超紧凑的代码，只需几行代码即可完成任务：

#include <iostream>
#include <string>
#include <sstream>
#include <utility>
#include <set>
#include <unordered_map>
#include <type_traits>
#include <iomanip>

// ------------------------------------------------------------
// Create aliases. Save typing work and make code more readable
using Pair = std::pair<std::string, unsigned int>;

// Standard approach for counter
using Counter = std::unordered_map<Pair::first_type, Pair::second_type>;

// Sorted values will be stored in a multiset
struct Comp { bool operator ()(const Pair& p1, const Pair& p2) const { return (p1.second == p2.second) ? p1.first<p2.first : p1.second>p2.second; } };
using Rank = std::multiset<Pair, Comp>;
// ------------------------------------------------------------

std::istringstream text{ " 4444 55555 1 22 4444 333 55555 333 333  4444  4444 55555  55555 55555 22 "};

int main() {

    Counter counter;
    
    // Count
    for (std::string word{}; text >> word; counter[word]++);

    // Sort
    Rank rank(counter.begin(), counter.end());

    // Output
    for (const auto& [word, count] : rank) std::cout << std::setw(15) << word << " : " << count << '\n';
}
于 2021-09-25T20:13:18.250 回答