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

public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        unordered_map<int, int> m;//方法一：哈希法，将数据出现次数存放在以哈希表为底层的数据结构中，缺点：空间换时间
        int ans;
        for(auto nums:numbers)
        {
            ++m[nums];
            if(m[nums]>numbers.size()>>1)
            {
                ans=nums;
            }
        }
        return ans;

        sort(numbers.begin(),numbers.end());//方法二：排序法，将数组排序后，出现次数超过数组一半的数据必然出现在数组中间位置
        return numbers[numbers.size()>>1];

        vector<int> vis(10001,0);//方法三：标记法，类似于桶排序的方法，将数据出现次数放入到向量组中，缺点：需要提前申请内存来，可能导致内存使用不充分
        int ans;
        for(auto nums:numbers)
        {
            ++vis[nums];
            if(vis[nums]>numbers.size()>>1)
            {
                ans=nums;
            }
        }
        return ans;

        int cnt=0;//方法四：登记法，使用整数型变量记录出现次数，使用另一个整型变量存放数据，缺点：需要遍历数组
        int res=0;
        for(int i=0;i<numbers.size();++i)
        {
            if(cnt==0) res=numbers[i];
            cnt+=(numbers[i]==res)?1:-1;
        }
        return res;
    }
};