题目：
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
限制：
1 <= 数组长度 <= 50000
注意：本题与 力扣169 题相同
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
方法一：哈希表
创建一个哈希表，遍历数组，用哈希表记录每个数字出现的次数，就可找出出现次数大于一半的数字。
1 class Solution { 2 public int majorityElement(int[] nums) { 3 int n = nums.length; 4 Map<Integer, Integer> map = new HashMap<>(); 5 for(int num : nums){ 6 map.put(num, map.getOrDefault(num,0)+1); 7 if(map.get(num) > (n / 2)){ 8 return num; 9 } 10 } 11 return 0; 12 } 13 }
小知识：
Map.getOrDefault(Object key, V defaultValue);
如果在Map中存在key，则返回key所对应的的value。
如果在Map中不存在key，则返回默认值。
例如：
map.put( num, map.getOrDefault(num, 0) + 1 )
①map中含有num的话，就将num对应的value值+1
②map中不含有num的话，num对应的value对应的默认值赋值为0，然后再+1
方法二：排序
题目中给了一定存在一个数字出现的次数超过数组长度的一半，故排序后，出现次数最多的数就在排序后数组的中间位置。
1 class Solution { 2 public int majorityElement(int[] nums) { 3 Arrays.sort(nums); 4 return nums[nums.length / 2]; 5 } 6 }
方法三：摩尔投票法
“假设数组中每个不同的数字就代表每一个国家，而数字的个数就代表这个国家的人数，他们在一起混战，就是不同国家之间每两个人数同归于尽。我们就可以知道哪个人数大于数组长度一半的肯定会获胜。”
详情可以看：K神老师的题解
思路：
①初始化： 票数统计 sum = 1 ， 众数 vit_num为数组第一个元素；
②循环： 从第二个数开始遍历数组 nums 中的每个数字 num ；
- 当 票数 sum 等于 0 ，则重新赋值sum = 1，且假设当前数字 nums[i] 是众数；
- 当 当前元素nums[i] == vit_num 时，票数 sum 自增 1 ；当 nums[i]!= x 时，票数 sum自减 1 ；
③返回值： 返回 vit_num 即可；
假设数组中不存在占一半以上的数字呢？
就需要加入一个 “验证环节” ，遍历数组 nums 统计 vit_num 的数量。
- 若 vit_num 的数量超过数组长度一半，则返回 vit_num ；
- 否则，返回未找到众数；
1 class Solution { 2 public int majorityElement(int[] nums) { 3 int n = nums.length,sum = 1; 4 int vit_num = nums[0]; 5 for (int i = 1; i < n; i++){ 6 if (sum == 0){ 7 sum = 1; 8 vit_num = nums[i]; 9 }else if (nums[i] == vit_num){ 10 sum++; 11 }else{ 12 sum--; 13 } 14 } 15 return vit_num; 16 } 17 }