数组中超过一半的数字（unordered_map/贪心）

/*
total 标记是否需要替换数字
最大贪心，前面为一半不一样数字，后面为超过一半的相同数字，最终记录的数字为最多的那个
因此如果超过一半数字存在，无论如何排列最终都会记录下排列最多的数字。
但是最后还要遍历数组看是否超过一半。
当比较下一个数字时，total 为 0时候替换数字为当前数字。
时间O(n) 空间：O(1)
*/
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> vt) {
        if(!vt.size()) return 0;
        int f, total = 0;
        for(int i = 0; i < vt.size(); i++){
           if(total == 0){
               f = vt[i];
               total = 1;
           }
           f == vt[i]?total++:total--;
        }
        total = 0;
        for( auto x :vt){
            if(f == x) total++; // 得到的最多个数的f，k可能凑巧在最后，还需要判断
        }
       return total > vt.size()/2 ? f : 0;
    }
};
/*
unordered_map 哈希表 要O(n)的空间
*/
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> vt) {
        unordered_map<int, int> mp;
        for(auto x : vt) ++mp[x];
        for(auto x : vt) {
            if(mp[x] > vt.size() / 2) return x;
        }
        return 0;
    }
};