线性时间投票algorithm。 我不明白
当我正在阅读（ find数组中最常见的条目 ）时，提出了Boyer和Moore的线性时间投票algorithm 。
如果您按照该网站的链接，则可以逐步解释algorithm的工作原理。 对于给定的序列， AAACCBBCCCBCC它提出了正确的解决scheme。
当我们将指针向前移动一个元素e：
- 如果计数器为0，我们将当前候选人设置为e，并将计数器设置为1。
- 如果计数器不是0，则根据e是否是当前候选者来递增或递减计数器。
当我们完成时，如果有多数，当前候选人是多数。
如果我在AAACCBB作为input的一张纸上使用这个algorithm， 那么build议的候选人将变成B ，显然是错的。
正如我所看到的，有两种可能性
- 作者从来没有在
AAACCBBCCCBCC以外的任何其他algorithm上尝试过他们的algorithm，完全是无能的，应该当场解雇（疑问） 。 - 我明显错过了一些东西 ，必须禁止从Stackoverflow，并再也不允许触摸任何涉及逻辑。
注意：下面是Niek Sanders algorithm的一个C ++实现 。 我相信他正确地实现了这个想法，因此它也有同样的问题（或不是吗？）。
该algorithm仅在该集合具有多数时才起作用 – 超过一半的元素是相同的。 在你的例子中AAACCBB没有这样的多数。 最频繁的字母出现3次，string长度是7。
小而重要的是对其他解释的补充。 摩尔的投票algorithm有两个部分 –
-
运行摩尔的投票algorithm的第一部分只给你一个候选人的多数元素。 在这里注意“候选人”一词。
-
在第二部分中，我们需要再次遍历数组来确定这个候选是否发生了最大次数（即大于/ 2次）。
第一次迭代是find候选者，第二次迭代是检查这个元素是否出现给定数组的大部分时间。
所以时间复杂度是： O(n) + O(n) ≈ O(n)
从第一个链接的SO问题来看：
具有数组中超过一半的条目等于N的属性
从Boyer和Moore页面：
如果存在这样的元素，那么序列中的哪个元素是大多数
这两种algorithm明确地假定一个元素至less出现N / 2次 。 （特别注意“多数”与“最常见”不一样。）
我为这个algorithm写了一个C ++代码
char find_more_than_half_shown_number(char* arr, int len){ int i=0; std::vector<int> vec; while(i<len){ if(vec.empty()){ vec.push_back(arr[i]); vec.push_back(1); }else if(vec[0]==arr[i]){ vec[1]++; }else if(vec[0]!=arr[i]&&vec[1]!=0){ vec[1]--; }else{ vec[0]=arr[i]; } i++; } int tmp_count=0; for(int i=0;i<len;i++){ if(arr[i]==vec[0]) tmp_count++; } if(tmp_count>=(len+1)/2) return vec[0]; else return -1; }
主要function如下：
int main(int argc, const char * argv[]) { char arr[]={'A','A','A','C','C','B','B','C','C','C','B','C','C'}; int len=sizeof(arr)/sizeof(char); char rest_num=find_more_than_half_shown_number(arr,len); std::cout << "rest_num="<<rest_num<<std::endl; return 0; }
当testing用例是“AAACCBB”时，该集合没有多数。 因为“AAACCBB”的长度是7，所以没有元素出现超过3次。
以下是“Boyer和Moore线性时间投票algorithm”的代码：
int Voting(vector<int> &num) { int count = 0; int candidate; for(int i = 0; i < num.size(); ++i) { if(count == 0) { candidate = num[i]; count = 1; } else count = (candidate == num[i]) ? ++count : --count; } return candidate; }
