统计数组元素出现次数

Question

我陷入了困境。我的问题是如何在一个整数数组中获取重复最多的数字，该数组的值可以从0到5,000。该数字应至少重复n/4次，其中n是数组长度。

我尝试过提取至少n/2次重复元素，但无法按照我的要求进行修改。此外，由于我的数组不是字符数组，所以我不能创建大小为5,000的数组来增加重复数字的索引。

- Chaithra

---

为什么不行？我无法创建一个大小为5000的数组以增加重复数字的索引。 - hmjd

如果是这样，那么你将如何读取大约5000*4字节=19kb的输入数组？ - P.P

@KingsIndian - 每个输入数字的范围为[0,5000]。但是输入的数字数量仅为n（根据OP）。 - ArjunShankar

0-5000的值范围至少需要13位。 13位*5000=65000位，即使您不浪费一位也几乎达到8kb。 要将其装入6kb内，您需要进行压缩。 - huseyin tugrul buyukisik

所以，您想要将该数字重复8次。 - huseyin tugrul buyukisik

Answer 1

这是我的处理方式，我认为针对这种问题很有意义：

1. （原地）排序数组，在拥有的情况下使用qsort()会更加简单。
2. 迭代遍历数组，并在每次数组值改变时重置计数器，一旦计数器达到n/4，记住它所对应的数字。
3. 完成。

这里重要的是，排序使得计算每个元素的次数变得容易，通过将所有相同的元素组合成一个序列，简化了计数过程。

- unwind

---

如果它实际起作用，我想这是可以的。谢谢。我会回来点赞的。 - Chaithra

但是 OP 要求出现次数而不是连续重复的次数。 - huseyin tugrul buyukisik

@tuğrulbüyükışık 排序后，结果是相同的。所有出现的元素将被分组成一个序列。例如：[1, 5, 4, 3, 1, 7, 2, 1] -> [1, 1, 1, 2, 3, 4, 5, 7]。 - unwind

是的。这样可以节省很多内存，而不需要使用不同的计数器。+1 - huseyin tugrul buyukisik

非常感谢解答……但是如果例如，2047重复出现了16次，而2012重复出现了10次，这个算法会返回2012，因为它首先找到了它，但是最重复的元素是2047。有什么想法吗？ - Chaithra

@Chaithra 编辑您的问题以反映需要找到最重复的数字，该数字也出现在超过n/4个位置。 - HonkyTonk