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

参考：https://blog.nowcoder.net/n/a9df4dee431a4d6c9cf080ba06fa439d
方法一：哈希表

链接：https://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163?answerType=1&f=discussion
来源：牛客网

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        unordered_map<int,int> mp;
        for (const int val : numbers) ++mp[val];
        for (const int val : numbers) {
            if (mp[val] > numbers.size() / 2 ) return val;
        }
        return 0;
    }
};

方法二：排序法：

链接：https://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163?answerType=1&f=discussion
来源：牛客网

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        sort(numbers.begin(), numbers.end());
        int cond = numbers[numbers.size() / 2];
        int cnt = 0;
        for (const int k :numbers) {
            if (cond == k) ++cnt;
        }
        if (cnt > numbers.size() / 2) return cond;
        return 0;
    }
};

方法三：候选法（最优解）

链接：https://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163?answerType=1&f=discussion
来源：牛客网

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int cond = -1;
        int cnt = 0;
        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 (const int k :numbers) {
            if (cond == k) ++cnt;
        }
        if (cnt > numbers.size() / 2) return cond;
        return 0;
    }
};