【算法题】6.求主元素

题目

已知⼀个整数序列A = (a0,a1,a2,...an-1),其中(0<= ai <=n),(0<= i<=n). 若存在ap1= ap2 = ...=apm = x,且m>n/2(0<=pk<n,1<=k<=m),则称x 为 A的主元素. 例如,A = (0,5,5,3,5,7,5,5),则5是主元素; 若B = (0,5,5,3,5,1,5,7),则A 中没有主元素,假设A中的n个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找出数组元素中的主元素,若存在主元素则输出该元素,否则输出-1.

题目大意：

主元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

输入：

[1,2,5,9,5,9,5,5,5]

输出：

5

解析：

摩尔投票算法

1. 维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；

2. 遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：

   如果 x 与 candidate 相等，那么计数器 count 的值增加 1；

   如果 x 与 candidate 不等，那么计数器 count 的值减少 1。

3. 在遍历完成后，candidate 即为整个数组的众数。

4. 遍历数组中，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;
}