著作权归作者所有. 商业转载请联系作者获得授权 非商业转载请注明出处.
如果我们把众数记为 $+1$ 把其他数记为 $−1$ 将它们全部加起来 显然和大于 $0$ 从结果本身我们可以看出众数比其他数多.
在遍历完成后 $candidate$ 即为整个数组的众数.
我们举一个具体的例子 例如下面的这个数组:
Boyer-Moore 算法的正确性较难证明 这里给出一种较为详细的用例子辅助证明的思路 供读者参考:
我们证明了 count 的值一直为非负 在最后一步遍历结束后也是如此;
由于 value 的值与真正的众数 maj 绑定 并且它表示"众数出现的次数比非众数多出了多少次" 那么在最后一步遍历结束后 value 的值为正数;