先自白一下心路历程hhhh，出现多次的数肯定随索引从左往右扩是不断更新的：
于是有了以下暴力求解：
class Solution {
public int majorityElement(int[] nums) {
if(nums.length == 1){
return nums[0];
}
int ans = 0;
HashMap set = new HashMap();
for(int i = 0; i < nums.length; i++){
if(!set.containsKey(nums[i])){
set.put(nums[i],1);
}else{
int cur = set.get(nums[i]);
ans = (i+1)/2 <= cur ? nums[i] : ans;
set.put(nums[i],++cur);
}
}
return ans;
}
}
虽然通过了用例，但是真的又慢空间消耗又大。
于是在评论区开始了学习：
直接排序：https://leetcode.cn/leetbook/read/top-interview-questions/xm77tm/?discussion=POk1ka
真是！这个怎么都没想到呢！！题中说了给定的数组总是存在多数元素。也就是说肯定有一个元素的个数大于数组长度的一半。我们只需要把这个数组排序，那么数组中间的值肯定是存在最多的元素。
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
位运算:
在java中int类型是32位的，我们只需要判断所有数字在某一位1的个数大于数组长度的一半，那么这个众数在这个位置肯定就是1，我们需要遍历32次，确定这个众数每个位置是0还是1即可。
public int majorityElement(int[] nums) {
int major = 0;
int length = nums.length;
//在java中int类型是32位，我们遍历每一位
for (int i = 0, mask = 1; i < 32; i++, mask <<= 1) {
//bitCounts表示所有数字在当前位置1的个数。比如当i=0
//的时候，我们可以认为他表示的是所有数字在二进制位
//中最右边1的总数。
int bitCounts = 0;
for (int j = 0; j < length; j++) {
//判断数字nums[j]的第i（i从0开始）个位置是否为1，
//如果是1，bitCounts就加1
if ((nums[j] & mask) == mask)
bitCounts++;
//如果bitCounts大于数组的一半，那么这个众数在
//这个位置肯定是1，然后通过 major |= mask运算
//把这个位置变为1，后面不需要再判断了，直接终止
//内层循环
if (bitCounts > length / 2) {
major |= mask;
break;
}
}
}
return major;
}
位运算相关
【右移运算符（>>）】：
将一个数的各二进制位全部右移若干位，正数左补0，负数左补1
【左移运算符（<<）】：
将一个运算对象的各二进制位全部左移若干位（左边的二进制位丢弃，右边补0）
【位与运算符（&）】：
参加运算的两个数据，按二进制位进行“与”运算；两位同时为“1”，结果才为“1”，否则为0
【按位或运算符（|）】：
参加运算的两个对象，按二进制位进行“或”运算；参加运算的两个对象只要有一个为1，其值为1。
【异或运算符（^）】
参加运算的两个数据，按二进制位进行“异或”运算；如果两个相应位为“异”（值不同），则该位结果为1，否则为0。
【取反运算符（~）】：
参加运算的一个数据，按二进制位进行“取反”运算；即将0变1，1变0。
摩尔投票法
假设数组中每个不同的数字就代表一个国家，而数字的个数就代表这个国家的人数，他们在一起混战，就是每两个两个同归于尽。我们就可以知道那个人数大于数组长度一半的肯定会获胜。
就算退一万步来说，其他的所有人都来攻击这个人数最多的国家，他们每两个两个同归于尽，最终剩下的也是那个众数。
//从左往右开始，第一个取到的数理所当然个数为1，开始与后面的数比较(因此i从1开始)；
//相同的++，不同的--；抵消归零了则选择下一位重新开始
//最后输出的即为众数
public int majorityElement(int[] num) {
int major = num[0];
int count = 1;
for (int i = 1; i < num.length; i++) {
if (count == 0) {
//前面都消完了，在重新赋值
count++;
major = num[i];
} else if (major == num[i]) {
//自己人，count就加1
count++;
} else {
//不是自己人就同归于尽，消掉一个
count--;
}
}
return major;
}
