什么是摩尔投票算法？
摩尔投票算法是一种使用线性时间和常数空间查找大部分元素序列的算法。它以1981年出版的Robert S. Boyer和J Strother Moore的名字命名，并且是流式算法的典型例子。
最简单的形式就是，查找输入中重复出现超过一半以上(n/2)的元素。如果序列中没有这种元素，算法不能检测到正确结果，将输出其中的一个元素之一。如果不能保证输入数据中有占有一半以上的元素，需要再遍历一下验证。
算法流程：
该算法在其局部变量中维护一个序列元素和一个计数器，计数器最初为零。然后，它一次一个地处理序列的元素。处理元素x时，如果计数器为零，则算法将x存储为其维护的序列元素，并将计数器设置为1。否则，它将x与存储的元素进行比较，并使计数器递增（如果相等）或递减计数器（不相等）。
这里有两个先觉条件要明确：
出现超过一半以上(n/2)的元素有且只有一个；
这个元素一定存在
这里先贴代码（swift）：
代码摘要：
我们维护一个局部变量作为当前查找元素，一个局部变量作为计数器，
当遍历开始的时候，此时计数（count）为0，则将数组第一个元素作为当前查找元素；
当遍历的元素与查找元素相等，计数加1；反之则-1；
若当计数为0时，将下一个元素作为当前查找元素，继续重复以上操作；当遍历结束时，当前查找元素则为目标元素。
网友评论