力扣每日一题 169. 多数元素

问题：给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

解决的问题是如何在任意多的候选人（选票无序），选出获得票数最多的那个。常见的算法是扫描一遍选票，对每个候选人进行统计的选票进行统计。当候选人的数目固定时，这个常见算法的时间复杂度为：O(n)，当候选人的数目不定时，统计选票可能会执行较长时间，可能需运行O(n2)的时间。当选票有序时，可以很容易编出O(n)的程序，首先找到中位数，然后检查中位数的个数是否超过选票的一半。这篇论文针对无序且侯选人不定的情形，提出了摩尔投票算法。算法的比较次数最多是选票（记为n）的两倍，可以在O(n)时间内选出获票最多的，空间开销为O(1)。

class Solution {

public:

    int majorityElement(vector<int>& nums) {

   int candidate=0,vote=0;  //candidate 为候选人 vote代表票数

   for(int i:nums){

       if(vote==0){

           candidate=i;

           vote=1;

       } else {

           if(i == candidate) {

               ++vote;

           } else if(i!=candidate){

               --vote;

           }

       }

   }

   return candidate;

    }

};