arrays - 如何计算 O(N) 中未排序整数数组的众数？

Question

...使用迭代过程(无哈希表)？

这不是家庭作业。模式是指最频繁的数字(统计模式)。我不想使用哈希表，因为我想知道如何迭代地完成它。

Answer 1

好的 Fantius，这个怎么样？

使用 RadixSort (BucketSort) 算法对列表进行排序(技术上为 O(N) 时间；数字必须是整数)。从第一个元素开始，记住它的值并从 1 开始计数。遍历列表，递增计数，直到达到不同的值。如果该值的计数高于当前高计数，请记住该值并将计数作为模式。如果您得到高数的平局，请记住两个(或所有)数字。

...是的，是的，RadixSort 不是就地排序，因此涉及可以称为哈希表(由当前数字索引的集合的集合)的东西。但是，哈希表是用来排序的，而不是用来计算模式的。

我要说的是，在一个未排序的列表上，如果不涉及哈希表，就不可能在线性时间内计算模式。在排序列表中，该算法的后半部分仅通过跟踪当前最大计数来工作。