Lie*_*ers 42 language-agnostic puzzle algorithm
当我读到这个(找到数组中最常见的条目)时,建议使用Boyer和Moore的线性时间投票算法.
如果您点击该站点的链接,则会逐步说明该算法的工作原理.对于给定的序列,AAACCBBCCCBCC它提供了正确的解决方案.
当我们将指针向前移动到元素e上时:
- 如果计数器为0,我们将当前候选设置为e,并将计数器设置为1.
- 如果计数器不为0,我们根据e是否是当前候选者来递增或递减计数器.
当我们完成时,如果存在多数,则当前候选者是多数元素.
如果我在一张纸上使用这个算法AAACCBB作为输入,建议的候选人将成为B显然是错误的.
我认为,有两种可能性
AAACCBBCCCBCC,完全不称职,应该当场解雇(怀疑).注意:这是Niek Sanders 的算法的C++实现.我相信他正确地实现了这个想法,因此它有同样的问题(或者不是吗？).
Raf*_*ird 45
该算法仅在集合占多数时才有效 - 超过一半的元素是相同的.AAACCBB在你的例子中没有这样的多数.最常见的字母出现3次,字符串长度为7.
Sri*_*aju 27
小但是对其他解释的重要补充.摩尔的投票算法有2个部分 -
运行摩尔投票算法的第一部分只为您提供了多数元素的候选者.请注意这里的"候选人"一词.
在第二部分中,我们需要再次迭代数组以确定该候选是否出现最大次数(即大于/ 2次).
第一次迭代是找到候选者,第二次迭代是检查这个元素是否在给定数组中大多数时间出现.
所以时间的复杂性是: O(n) + O(n) ? O(n)
从第一个链接的SO问题:
具有该属性的数组中超过一半的条目等于N.
来自Boyer和Moore页面:
如果存在这样的元素,则序列的哪个元素占多数
这两种算法都明确假设一个元素至少发生N/2次.(特别注意"多数"与"最常见"不同.)