c - 确定每个元素在数组中出现的频率？

Question

关闭。这个问题需要多问 focused 。目前不接受答案。

---

想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post .

已关闭 7 年前。

Improve this question

是否有一种高效的 C 算法来计算和报告数组中相等元素的数量

例如，如果我们有

int Z[] = { 4, 9, 4, 10, 4, 2,  10, 1, 19, 21, 21 };

那么结果应该是

elem         number
  4            3
  9            1
  10           2
  2            1
  1            1
  19           1
  21           2

Answer 1

有很多方法可以做到这一点，每种方法都有不同的性能权衡。

首先，您可以对数组执行双重 for 循环，并为每个元素计算它出现的次数。这将花费时间 O(n²)，其中 n 是数组元素的数量。然而，它只需要空间 O(1)。

其次，您可以将数组按升序排序，这会将相同的元素组合在一起。从那里，可以很容易地看到每个元素出现的次数，因为您可以遍历数组一次并计算每个元素连续出现的次数。所使用的运行时间和空间取决于您对数组进行排序的方式。如果使用堆排序，运行时间将为 O(n log n)，而空间使用量仅为 O(1)。如果您碰巧知道数组中所有元素的范围从 0 到 U(含)，则可以使用时间 O(n + U) 和空间 O(U) 的计数排序或时间 O(n log U) 和空间的基数排序O(n)。

第三，您可以构建一个存储每个元素频率的辅助表，并通过遍历数组一次来填充它，并随时填充条目。如果使用哈希表，预期运行时间将为 O(n)，空间使用量也将为 O(n)。如果您知道数组元素在 0 到 U(含)范围内，则可以使用频率数组并在时间 O(n + U) 和空间 O(U) 中解决此问题(本质上，这将是计数排序! )

这里没有明显的赢家。对于空间使用量为 O(1) 的事物，堆排序具有最佳的时间复杂度。散列的总体时间复杂度最好，但空间利用率较差。计数或基数排序可能是最好的，具体取决于数字的大小。

根据您的情况，看看您的实际参数是什么，希望您能选择当前最适合您的解决方案。