查询区间中出现次数超过长度的一半的数字

思路：思路有很多，大致有这几种：

强行在线统计每个数字的出现次数，由于不知道数字的规模，用键值树（hash_map、Tree_map）记录次数，复杂度 $O (n l o g n)$ ；
利用排序的，如果某个数超过数组长度的一半那么它必然在中间位置mid出现，于是排序完我们可以扫一遍统计该数字的出现次数，复杂度 $O (n l o g n)$ ;
类似于在线找区间最大子段和的思路，动态地记录每个数字的频度，每当出现与该数字不同的数字就-1，否则+1。如果该数字出现的次数超过数组长度的一半，那么最后频度一定大于等于1，并且对应着该数字。为了防止更新后频度大于等于1的那个数字恰好是刚刚被更新的，所以扫一遍数组检查合法性。复杂度 $O (n)$ 。

Code：

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        //O(nlogn)
        /* map<int, int> mp; mp.clear(); if (numbers.size() == 1) return numbers[0]; for (int i = 0; i < numbers.size(); i++) { if (!mp.count(numbers[i])) mp.insert(make_pair(numbers[i], 1)); else { mp[numbers[i]]++; if (mp[numbers[i]] > numbers.size() / 2) { return numbers[i]; } } } return 0; */
        //O(n)
        int count = 0, point;
        for (int i = 0; i < numbers.size(); i++) {
            if (count == 0) count = 1, point = numbers[i];
            else if (point == numbers[i]) ++count;
            else --count;
        }
        count = 0;
        for (int i = 0; i < numbers.size(); i++) {
            if (point == numbers[i]) ++count;
        }
        return count > numbers.size() / 2 ? point : 0;
    }
};