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

排序，返回中间坐标位置元素值

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        //排序，返回中间坐标位置元素值
        sort(numbers.begin(), numbers.end());
        return numbers[numbers.size()>>1];

    }
};

哈希

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        //哈希
        unordered_map<int,int> hash;
        int res = 0, len = numbers.size();
        for(int i = 0; i < len; i++){
            hash[numbers[i]]++;
            //不必等到哈希表完全建立再进行此判断
            if(hash[numbers[i]] > len>>1)
                res = numbers[i];
        }
        return res;
    }
};

摩尔根投票法

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        //摩尔根投票法
        int res = 0, count = 0;
        for(int i = 0; i < numbers.size(); i++){
            if(count == 0){
                res = numbers[i];
                count++;
            }
            else
                res==numbers[i] ? count++:count--;
        }
        return res;
    }
};