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

class Solution {
  public:
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        if (numbers.empty()) return 0;

        int candidate = numbers[0];
        int count = 1;

        // 第一遍遍历：找出候选数字
        for (int i = 1; i < numbers.size(); i++) {
            if (count == 0) {
                candidate = numbers[i];
                count = 1;
            } else if (numbers[i] == candidate) {
                count++;
            } else {
                count--;
            }
        }

        // 第二遍遍历：验证候选数字确实超过一半
        // 虽然题目保证有解，但为了代码健壮性还是验证一下
        count = 0;
        for (int num : numbers) {
            if (num == candidate) {
                count++;
            }
        }

        return count > numbers.size() / 2 ? candidate : 0;
    }
};