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

候选法

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
      int cnt = 0, cond = -1;
      
      //  候选法选出来的肯定是众数
      for (int i = 0; i < numbers.size(); ++i) {
        if (cnt == 0) {
          cond = numbers[i];
          ++cnt;
        } else {
          if (cond == numbers[i]) {
            ++cnt;
          } else {
            --cnt;
          }
        }
      }
      
      cnt = 0;
      
      for (auto const &it : numbers) {
        if (it == cond) {
          ++cnt;
        }
      }
      
      return cnt > (numbers.size() >> 1) ? cond : 0;
    }
};