Solution

• 投票法

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int candidate = 0, votes = 0;
        for (int num : numbers) {
            if (votes == 0) candidate = num;
            if (num == candidate) {
                votes++;
            } else {
                votes--;
            }
        }
        
        // 确认剩余的候选人是否超过一半
        votes = count(numbers.begin(), numbers.end(), candidate);
        return votes > numbers.size()/2 ? candidate : 0;
    }
};

• 借助map保存

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if (numbers.size() == 0) return 0;
        int flag = numbers.size()/2 + 1;
        int res = 0;
        unordered_map<int, int> umap;
        for (int num : numbers) {
            umap[num]++;
        }
        for (auto iter = umap.begin(); iter != umap.end(); ++iter) {
            if (iter->second >= flag) {
                res = iter->first;
                break;
            }
        }
        return res;
    }
};