Boyer-Moore投票算法

【问题描述】这是一道2013年考研真题，已知一个整数序列A长度为N，其中若存在a，且a的个数大于N/2，则称a为A的主元素

例如：3 5 5 3 5 7 5 5，其主元素为5

又如：3 5 5 3 5 1 5 7，其中没有主元素。

假设元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出主元素。若存在主元素则输出该元素否则输出

要求时间复杂度为O(N)，请注意穷举法时间复杂度是O(N^2)，排序再遍历查找的时间复杂度是O(N*logN+N)

【输入形式】

一个整数数组，以0作为结束输入

【输出形式】

主元素，若没有则输出-1

【样例输入】

3 5 5 3 5 7 5 5 0

【样例输出】

5

【样例说明】长度为8，共有5个‘5’
先放完整代码：

#include <iostream>
using namespace std;
int major(int *nums, int len)
{
    int candidate = -1;int count = 0;for (int i = 0; i < len; i++){
    if (count == 0){
    candidate = nums[i];}if (nums[i] == candidate){
    count++;}else{
    count--;}}count = 0;for (int i = 0; i < len; i++){
    if (nums[i] == candidate){
    count++;}}return count * 2 > len ? candidate : -1;
}int main()
{
    int a[100],temp,len=0;cin >> temp;while (temp != 0){
    a[len] = temp;len++;cin >> temp;}cout << major(a,len);
}

这种算法的主要原理是，主要元素必须超过总元素的一半，即主要元素出现的次数要大于其他所有元素之和，在遍历中两两抵消，最后要满足count>=1。
由于不一定会出现主要元素，第一次遍历后选出来的可能是主要元素，也可能是其他数据，所以要第二次遍历来计数，如果满足了count*2大于数组长度，此时candidate这个数据才是主要元素。