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

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

一、排序+验证
时间复杂度不符合要求了，虽然也能跑过。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        sort(numbers.begin(), numbers.end());
        return numbers[numbers.size() / 2];
        // 虽然这也能通过，但这是因为牛客的测试用例比较少的缘故 有些特殊情况没有考虑
    }
};

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        // 考虑为空的清空
        if(numbers.empty())
            return 0;
        sort(numbers.begin(), numbers.end()); // 排序
        int midNum = numbers[numbers.size()/2];
        int count = 0;
        for(int i = 0; i < numbers.size(); ++i)
            if(midNum == numbers[i])
                ++count;
        if(count > numbers.size()/2) // 判断是否出现次数超过一半
            return midNum;
        else
            return 0;
    }
};

二、众数非众数互相抵消

出现次数大于数组长度一半的数记为众数，其他的数则是非众数。

遍历，逐个比较前后2个数，如果2个数不相等，互相抵消。

最坏情况下，每次消去一个众数和非众数，如果存在众数，那么最后剩下的就一定是众数。

当然，可能数组中没有众数，因此还需要验证一下是否为众数。

如何相互抵消呢？利用一个count，把第一个数给ret，此时count为1，继续遍历，判断当前数与ret是否相等，相等++count，不相等抵消掉，也就是--count

复杂度为

class Solution {
    public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.empty())// 考虑为空的清空
            return 0;
        int ret = numbers[0];
        int count = 1; // 出现的次数，默认为一次
        for(size_t i = 1; i < numbers.size(); ++i){
            if(count != 0){ // count > 1时，通过--count就能达到抵消效果
                if(numbers[i] == ret)
                    ++count;
                else // 不相等
                    --count;
            }else{ // count为0需要更新ret
                ret = numbers[i];
                count = 1;
            }
        }
        count = 0; // 验证是否为众数
        for(int i = 0; i < numbers.size(); ++i)
            if(ret == numbers[i])
                ++count;
        if(count > numbers.size()/2) // 判断是否出现次数超过一半
            return ret;
        else
            return 0;
    }
};