c - 哈希表中某些消息的百分比

Question

我正在寻找一种可以帮助我完成此任务的算法：我需要用 C 语言编写一个程序，该程序将从发送者到接收者的消息数量未知。就像 23 到 12、44 到 19 等一样，我需要返回所有负责超过 10% 消息的发送者\接收者。我被允许使用哈希表。

谢谢

Answer 1

本文描述了一个算法。
它不使用哈希表，只是一个包含 10 个条目的简单数组（因为 10% = 1/10）。
它不是 100% 准确的——它肯定会找到使用 10% 的那些，但也可能会找到一些使用少于这个的。

算法的简要说明：

1. 维护一个包含 10 个项目和计数器的列表。最初列表是空的。
2. 对于输入中的每个项目，如果它在列表中，则增加计数。
3. 如果没有，请将其添加到列表中，计数为 1。
4. 如果此添加使列表长度超过 10，则减少列表中所有元素的计数，并删除那些下降到 0 的元素。确保列表将返回到 10 或更小的大小。