arrays - 数组中的十进制显性数

Question

最近我遇到了这个面试题:

给定数组中的 n 个实数。数组中的数字如果在数组中出现超过 n/10 次，则称为十进制显性数。给出一个 O(n) 时间的算法来确定给定的数组是否具有小数显性。

现在我可以想出几种方法来解决这个问题，以及这个问题的任何概括(即找到在数组中出现 K 次的任何数字)

一种可能是在第 1 遍中创建一个哈希表，然后在第 2 遍中计算出现的次数，这将是 O(n)，但也使用 O(n) 空间，

有一种方法using 9 buckets

但是，我们有什么办法可以在一个恒定的空间中做到这一点吗？有什么建议吗？？

[编辑] 我还没有检查过 9 桶的解决方案，读者可能喜欢阅读下面 n.m. 的评论

Answer 1

我已经概述了一种基于 Boyer-Moore 多数投票算法的方法 here .

您记得(最多)(m-1) 个最近比其他元素更频繁出现的元素和相关计数。当看到一个记住的元素时，它的计数就会增加。当看到一个未记住的元素时，如果有一个空闲槽，则记住它并将其计数设置为 1，否则从所有已记住元素的计数中减去 1。忘记了计数为 0 的已记住元素。任何以高于 1/m 的比例出现的元素都是记住的元素之一。如果您事先不知道有 m-1 元素出现超过 n/m 次，您需要第二次通过来计算记住的元素的出现次数。

编辑:访问指定页面后，我看到它是完全相同的解决方案，只是它没有考虑到内存的非支配因素。

Once this has been finished any count variables with counts greater than 1 have more than 10 instances of themselves in the list.

不正确，但所有十进制显性数都将在末尾以计数 >= 1 被记住。我没有检查那里的代码，所以它可能包含错误，但算法是正确的，除了缺少检查通过。

如果我们有第二遍，所提出的反例会得到正确处理，状态会演化

0 1 2 3 4 5 6 7 8
1 1 1 1 1 1 1 1 1   // coming 9
0 0 0 0 0 0 0 0 0   // all forgotten, no slots occupied, coming 10
10 - - - - - - - -
 1 - - - - - - - -  // coming 0
10 0 - - - - - - - 
 1 1 - - - - - - -

最后有两个slot被占用，10和0都被记为1，10不是十进制显性，0是，而且是唯一的，后面会验证第二次检查通过。