相关疑难解决方法(0)

当我读到这个(找到数组中最常见的条目)时,建议使用Boyer和Moore的线性时间投票算法.

如果您点击该站点的链接,则会逐步说明该算法的工作原理.对于给定的序列,AAACCBBCCCBCC它提供了正确的解决方案.

当我们将指针向前移动到元素e上时:

• 如果计数器为0,我们将当前候选设置为e,并将计数器设置为1.
• 如果计数器不为0,我们根据e是否是当前候选者来递增或递减计数器.

当我们完成时,如果存在多数,则当前候选者是多数元素.

如果我在一张纸上使用这个算法AAACCBB作为输入,建议的候选人将成为B显然是错误的.

我认为,有两种可能性

1. 作者从未在其他任何事情上尝试过他们的算法AAACCBBCCCBCC,完全不称职,应该当场解雇(怀疑).
2. 我显然遗漏了一些东西,必须从Stackoverflow中被禁止,并且再也不允许触及任何涉及逻辑的东西.

注意:这是Niek Sanders 的算法的C++实现.我相信他正确地实现了这个想法,因此它有同样的问题(或者不是吗？).

给定一个包含N个元素的数组.我们知道其中一个元素至少重复N/2次.

我们对其他元素一无所知.它们可能重复或可能是唯一的.

有没有办法找出在一次通过中重复至少N/2次的元素,或者可能是O(N)？

没有额外的空间可供使用.

存在具有重复超过N/2个时间的元素的阵列(大小为N),并且阵列中的其余元素也可以重复,但是仅重复一个元素超过N/2次.找到号码.

我可以想到几种方法:

• 天真,保持哈希映射中每个数字的计数.
• 最简单的是,排序数组和n/2 + 1索引处的数字是所需的数字.
• 保持仅查找连续重复值的计数.单独检查交替存储值的模式.

无法想到更好的解决方案,必须有.

我已经读过这个问题 找到一个数组中最常见的条目

jon双向飞碟的回答只是让人心旷神怡...... :)

现在我试图解决这个问题找到一个在数组中出现超过n/3次的元素.

我很确定我们不能应用相同的方法,因为可能有2个这样的元素会发生超过n/3次并且会给出错误的计数警报.所以我们有什么方法可以调整jon双向飞碟的回答为此工作..？

或者是否有任何解决方案将在线性时间内运行？

给定n个整数的数组,其中一个元素出现超过n/2次.我们需要在线性时间和恒定的额外空间中找到该元素.

YAAQ:另一个阵列问题.