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

除了同归于尽法、map法和排序法以外，还可以有另一个方法，核心思想是顺序遍历数组，对当前下标之后的数字进行内循环统计出现次数。首先创建数组arr，赋初值1，长度等于数组的size，其记录的是数字出现次数，外循环数组，内循环 i 之后的数字，碰到相等数字则对首次出现位置上arr值+1，并且对相等数所对应arr上的值赋值为-1。内外循环均跳过arr[]=-1。在最好情况下即第一个数字就是答案，查找长度为n（或者n/2+1)，时间复杂度为O(n)；最坏情况下前一半的数字都不是答案且均不相同，此时代码的时间复杂度达到O(n²)，总体来说效率较低，属于新手答案。具体代码如下

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int n=numbers.size();
        vector<int> cou(n,1);
        for(int i=0;i<n;i++){
            if(cou[i]==-1)
                continue;
            for(int j=i+1;j<n;j++)
                if(cou[j]!=-1&&numbers[i]==numbers[j]){
                    cou[i]++;
                    cou[j]=-1;
                }
            if(cou[i]>n/2)
                return numbers[i];
        }
        return 0;
    }
};