Boyer–Moore投票算法

背景：

​ ���象着这样一个画面：会议大厅站满了投票代表，每个都有一个牌子上面写着自己所选的候选人的名字。然后选举意见不合的（所选的候选人不同）两个人，会打一架，并且会同时击倒对方。显而易见，如果一个人拥有的选票比其它所有人加起来的选票还要多的话，这个候选人将会赢得这场“战争”，当混乱结束，最后剩下的那个代表（可能会有多个）将会来自多数人所站的阵营。但是如果所有参加候选人的选票都不是大多数（选票都未超过一半），那么最后站在那的代表（一个人）并不能代表所有的选票的大多数。因此，当某人站到最后时，需要统计他所选的候选人的选票是否超过一半（包括倒下的），来判断选票结果是否有效。

（）

用途

找大多数。

Boyer-Moore投票算法步骤

1. 分组阶段：两个不同选票的人进行对抗，当剩下的人都是同一阵营时，分组结束。

   （）

   简化：只需要记住候选者的名字和目前票数，每遇到一个不同候选者，目前票数-1，反之则+1，当票数归0时，更换候选者为当前候选者，并将票数置为

2. 检验：对最后剩下的票数进行检验，验证的确超过一半

思想及正确性证明

​ 减治的思想，即如果原集合 S S S中有众数 m m m,那么删去两个不同元素后的集合 S ′ S' S′中众数仍然为 m m m,即最终剩下的元素一定为答案(如果众数存在)。

​ 更通俗的说，众数的性质决定了它的出现次数要多于其余数字，如果最终count为负数或为0，则说明不存在众数，在这种情况下，candidate是一个随机数。

数学证明：

每次从序列里选择两个不相同的数字删除掉（或称为「抵消」），最后剩下一个数字或几个相同的数字，就是出现次数大于总 数一半的那个元素。假设我们当前数组中存在次数大于总数一半的元素为 x x x，数组的总长度为 n n n，则我们可以把数组分为两部分，一部分为相同的 k k k个元素 x x x，另一部分为 n − k 2 \frac{n-k}{2} 2n−k​ 对个不同的元素配对，此时我们假设还存在另外一个次数大于总数一半的元素 y y y，则此时 y y y 因该满足 y > n 2 y>\frac{n}{2} y>2n​ ，但是按照我们之前的推理 y y y 应当满足 y ≤ n − k 2 y \le \frac{n-k}{2} y≤2n−k​ ，二者自相矛盾。

简单实现

int majority(vector& nums){
  int candidate,count=0;
  int n =nums.size();
  for(int i =0;i
    if(count==0){
      candidate=nums[i];
    	count=1;
    }
    count+=(nums[i]==candidate)?1:-1;
  }
  if(count
    if(nums[i]==candidate)
      check++;
  }
  return check(n/2)?candidate:-1;
}

    int n = nums.size();
    vector
        bool equal = false;//检验是否与candidates里的数相等
        for (int j = 0; j  0 && check[j] > n / (m + 1))
            ans.push_back(candidates[j]);
    }
    return ans;
}

复杂度

时间复杂度： O ( n m ) O(nm) O(nm),实际上，m大多数情况是一个常数，则也是线性的

空间复杂度： O ( m ) O(m) O(m),同理，m大多数情况是一个常数，故是常数级的

练习

169. 多数元素 - 力扣（LeetCode）

229. 多数元素 II - 力扣（LeetCode）