题目
已知⼀个整数序列A = (a0,a1,a2,...an-1),其中(0<= ai <=n),(0<= i<=n). 若存在ap1= ap2 = ...=apm = x,且m>n/2(0<=pk
题目大意：
主元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
输入：
[1,2,5,9,5,9,5,5,5]
输出：
5
解析：
摩尔投票算法
维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；
遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：
如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
如果 x 与 candidate 不等，那么计数器 count 的值减少 1。
在遍历完成后，candidate 即为整个数组的众数。
遍历数组中，candidate出现的次数是否大于n / 2，大于返回candidate ，否则返回-1。
复杂度分析
时间复杂度：
空间复杂度：
代码
int MainElement(int *A,int n){
int count = 0;
int key = A[0];
for (int i = 0; i < n; i++)
{
if (A[i] == key)
{
/* code */
}else{
if (count > 0)
{
count--;
}else{
key = A[i];
count = 1;
}
}
}
if (count > 0)
{
for (int i =count= 0; i < n; i++)
{
if (A[i] == key)
{
count++;
}
}
}
if (count > n / 2)
{
return key;
}
return -1;
}
