题解 | #数组中出现次数超过一半的数字#

//这是2013年408真题中的求主元素。
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
    int main = numbers[0];  //先设主元素为数组第一个元素
    int cnt = 1;   //而且计数为1
    int i = 0;
    for(i = 1; i < numbers.size(); i++)
    {
        if(numbers[i] == main)  //依次访问，如果与当前主元素相同
            cnt++;  //则计数加1
        else{
            if(cnt > 0)  //如果不是该主元素，且计数仍旧大于0
                cnt--;  //则计数减1
            else{        //如果不是主元素，且计数小于等于0
                main = numbers[i];    //就切换主元素，设当前访问元素为主元素
                cnt = 1;  //重新计数为1，开始下一趟循环
            }
        }
      }
      if(cnt > 0)    //全部访问完后再验证最后剩下的元素是否真为主元素
          for( i =0, cnt =0; i < numbers.size(); i++)
              if(numbers[i] == main)
                  cnt++;   //统计该元素出现次数
      if(cnt > numbers.size() / 2)  //次数超过一半则为主元素
          return main;
      else
          return 0;  //若该数出现次数不大于一半，则数组中不存在主元素
    }
};