gpt4 book ai didi

algorithm - 线性时间投票算法。我不明白

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:13:18 25 4
gpt4 key购买 nike

当我阅读这篇文章(Find the most common entry in an array)时,Boyer and Moore's Linear Time Voting Algorithm有人建议。

如果您点击该站点的链接,将逐步解释该算法的工作原理。对于给定的序列,AAACCBBCCCBCC 它给出了正确的解决方案。

When we move the pointer forward over an element e:

  • If the counter is 0, we set the current candidate to e and we set the counter to 1.
  • If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.

When we are done, the current candidate is the majority element, if there is a majority.

如果我在一张纸上使用此算法,以 AAACCBB 作为输入,建议的候选将变为 B,这显然是错误的。

在我看来,有两种可能

  1. 作者从未在 AAACCBBCCCBCC 以外的任何地方尝试过他们的算法,完全无能,应该当场解雇(怀疑)
  2. 我显然遗漏了一些东西,必须被禁止使用 Stackoverflow,并且再也不允许接触任何涉及逻辑的东西。

注意:这是一个C++ implementation of the algorithm来自尼克·桑德斯。我相信他正确地实现了这个想法,因此它有同样的问题(或者没有?)。

最佳答案

该算法仅在集合占多数时才有效——超过一半的元素相同。 AAACCBB 在你的例子中没有这样的多数。出现次数最多的字母出现3次,字符串长度为7。

关于algorithm - 线性时间投票算法。我不明白,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/780937/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com