题目描述；

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

思路一：哈希表

class Solution {
public:
  	int MoreThanHalfNum_Solution(vector<int> numbers) {
      	if (numbers.size() == 0) return numbers[0];
      	unordered_map<int, int> mp;
      	int res = 0, cnt = 0;
      	for (int& num : numbers) {
          	++mp[num];
          	if (mp[num] > cnt) {
              	res = num;
              	cnt = mp[num];
            }
        }
      	return res;
    }
}

时间复杂度：O(n)，空间复杂度：O(n)
提交结果：答案正确 运行时间：9ms 占用内存：1408KB 
使用语言：C++ 用例通过率：100.00%

思路二：Boyer-Moore 投票算法

class Solution {
public:
  	int MoreThanHalfNum_Solution(vector<int> numbers) {
      	int candidate = -1;
      	int count = 0;
      	for (int& num : nums) {
          	if (num == candidate) ++count;
          	else if (--count < 0) {
              	candidate = num;
              	count = 1;
            }
        }
      
      	return candidate;
    }
}

😿😿😿😿😿😿