本题讨论一个数组中元素出现的次数，如果一个元素出现的次数大于长度的一半时，此时称这个元素为主元素

常规的方法有排序法和哈希表

哈希表的时间复杂度和空间复杂度均为O(n),显然不是最优解

排序法的时间复杂度为O(nlogn),空间复杂度为O(1)，显然也不是最优解

今天给大家介绍一种时间复杂度为O(n),空间复杂度为O(1)的算法，摩尔投票法

1.算法的基本设计思想。

把一个元素当成一个候选人，出现的次数当成投的票数，通过遍历整个数组，如果候选人不一样的话;就让票数相互抵消,最后剩下的可能是主元素，然后再次遍历查找主元素出现的次数，如果大于一半的话就是主元素

2.代码的实现(C语言)

#include<stdio.h>
#define Max 10
typedef struct
{
    int data[Max];
    int length;
}List;
void InitList(List* L1)//初始化
{
    L1->data[0] = 0;
    L1->data[1] = 5;
    L1->data[2] = 5;
    L1->data[3] = 3;
    L1->data[4] = 5;
    L1->data[5] = 7;
    L1->data[6] = 5;
    L1->data[7] = 5;
    L1->length = 8;
}
int MajorList(List* L1)//核心函数
{
    int candidate = 0;
    int vote = 0;
    int i;
    int num = 0;
    for (i = 0; i < L1->length; i++)
    {
        if (vote == 0) //如果vote为0的话表示元素均已抵消完
        {
            candidate = L1->data[i];//把本元素看做一个候选人
        }
        if (candidate == L1->data[i])//如果两个元素一样的话，令票数+1
        {
            vote++;
        }
        else
            vote--;//如果不一样需要-1抵消
    }
    for (i = 0; i < L1->length; i++)
    {
        if (L1->data[i] == candidate)
            num++;
    }
    if (num > L1->length / 2)
        return candidate;
    else
        return -1;
}

int main()
{
    List L1;
    InitList(&L1);
    if (L1.length == 0)
        return 0;
    printf("%d ",MajorList(&L1));

    return 0;
}

3.复杂度

时间复杂度O(n)

空间复杂度O(1)