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

【题目解析】：要求 时间复杂度：O(n) 空间复杂度：O(1)

方法一：此题约定了空间复杂度为O(1)，则注定不能用hash法。那么最快速的方法就是排序，因为该数字超过数组一半长度，那么排序之后，该数字一定处于数组的中间位置，则两行代码即可。这里也给出hash的做法。

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        /*//选择+快排(如果是面试，排序要能兜住面试官) 
        sort(numbers.begin(),numbers.end());  
        return numbers[numbers.size()/2];
        */
        
        //但基于快排的排序空间复杂度必然不是O(1),且这里不需要完整排序
        //可以使用topk问题，k为n/2，时间复杂度可以降到O(n)
        //这里先不写，复习的时候写，面试说个思路应该也可以过
    }
};

//时间复杂度：O(n)
//空间复杂度：O(n)
class Solution {
public:
    //这个牛客也可以通过，可能是因为体型比较老，用例也不全面，没有判断空间复杂度的用例
    //用rangebase for 可以简洁一些
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        unordered_map<int,int> hash;
        for(int i = 0; i < numbers.size();++i)
        {
            hash[numbers[i]]++;
        }
        int n = numbers.size()/2;
        int i;    
        for(i = 0; i < numbers.size();++i)
        {
            if(hash[numbers[i]] > n)
                break;
        }
        return numbers[i];
    }
};

方法二：众数或者候选人方法，确实挺生动的，思路就是：相互抵消。

逻辑是：从前往后选数（同时记录这个数出现的次数），遇到相同的次数就加一，遇到不同的次数就减一，如果遇到相同的次数就加一，如果次数为零，说明这个数不是众数，就将下一个数作为候选人。当遍历完成，这个候选人就是众数。

其实类似的方法也可以用栈实现，相同就入栈，不同就出栈，最后元素就是栈顶元素。思想一模一样。

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int cur = 0,count = 0;
        for(int i = 0; i<numbers.size();++i)
        {
            if(count == 0)
            {
                cur = numbers[i]; //cur就是候选人
                count++;
            }
            else{
                if(cur == numbers[i])
                    count++;
                else
                    count--;
            }
        }
        return cur;       
    }
};