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

#include <unordered_map>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        // write code here
        unordered_map<int, int> mp;
        for(int i = 0; i < numbers.size(); ++i){
            ++mp[numbers[i]];
            if(mp[numbers[i]]>=((numbers.size()+1)/2)) return numbers[i];
			//正确题意 if(mp[numbers[i]]>(numbers.size()/2)) return numbers[i];
        }
        return 0;
    }
};

题目中是超过一半，我这里等于也过了，因为题目“保证数组输入非空，且保证有解”，思路就是记录目前位置值已经出现多少次了，超过一半就返回当前值。时间复杂度O(n)，空间复杂度O(n)。

官方题解有一个很妙的思路是排序后看中间，因为要过一半必然有中间那个。时间复杂度是O(nlogn)，空间复杂度是O(1)（如果是快排）

还有一个很妙的官方题解思路是利用超过一半可以把其他部分抵消了还有剩余的，因为保证有解，所以我只写了找到的情况，没有检验找到的不是。

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型vector
     * @return int整型
     */
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        // write code here
        int cond = -1, cnt = 0;
        for (int i = 0; i < numbers.size(); ++i) {
            if (cnt == 0) {
                cond = numbers[i];
                ++cnt;
            }
            else{
                if(cond==numbers[i]) ++cnt;
                else --cnt;
            }
        }
        return cond;
    }
};

时间复杂度O(n)，空间复杂度O(1)。