数组中的十进制主数

Question

最近我遇到了这个采访问题:

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

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

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

有一种方法可以使用9个桶

但是,我们有什么方法可以在一个恒定的空间里做到这一点？有什么建议？？

[编辑]我还没有检查过9桶解决方案,读者可能想通过下面的nm评论

Answer 1

我所概述基础上,博耶-穆尔多数表决算法的方式在这里.

你记得(最多)(m-1)最近比其他元素和相关数量更常见的元素.当看到记住的元素时,其计数会增加.当看到一个未记忆的元素时,如果有一个空闲的插槽,你会记住它并将其计数设置为1,否则你从记忆元素的所有计数中减去1.忘记了计数为0的记忆元素.任何元素的比例都高于1/m记忆元素之一.如果您不知道某些m-1元素出现次数超过n/m,则需要第二遍来计算记住元素的出现次数.

编辑:在访问指示的页面后,我看到它是完全相同的解决方案,除了它没有考虑到记住的非支配者.

完成此操作后,任何计数大于1的计数变量在列表中都有超过10个自身实例.

是不正确的,但所有小数的支配者都会记住>= 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 - - - - - - -

最后,有两个插槽被占用,10和0都被记住,计数为1. 10不是十进制显性,但是0是,而且它是唯一的,因为将通过第二个检查通道验证.

Answer 2

1. 执行循环并将值存储/添加到实数数组 int[] 中。

2. 如果数组列表值大于 1，则执行另一个循环，将数组列表值除以 10。