给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
提示：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/majority-element
解法1：无脑解法，不思考，利用空间，计算出来次数多次的元素。
class Solution {
public int majorityElement(int[] nums) {
//通过hashMap存储，找到数组中出现频率最高的数字
Map<Integer,Integer> map = new HashMap<>();
for(int i =0;i< nums.length; i++){
int temp = nums[i];
map.put(temp,map.getOrDefault(temp,0)+1);
}
//计算map中的最大值
int max = Integer.MIN_VALUE;
for(Map.Entry<Integer,Integer> entry: map.entrySet()){
if(entry.getValue() > max){
max = entry.getValue();
}
}
//找到最大值对应的key
for(Map.Entry<Integer,Integer> entry: map.entrySet()){
if(entry.getValue() == max){
return entry.getKey();
}
}
return 0;
}
}由于写解答是在leecode上直接写，也暴露出对map的常用方法的缺失，例如：map.entrySet()方法，或者是Map.Entry<Integer,Integer> .甚至是Integer.MIN_VALUE.都是对无idea编写的考研。
最后虽然能够解答成功，但是空间复杂度不尽如人意，是O(n)，那么我们思考下怎么将空间复杂度优化为O(1)？
我觉得还是要继续审题，问题的关键点在2/n上。
最终的最终，还是看了题解，那么我们一起来了解一下解题方法：
我这里参考的不是官方正式答案，而是其中一个题解，我感觉很有意思，也很好理解
简称：“同归于尽消杀法”
例如：有100个人，可能这100中有2个队伍或者3个队伍，或者4个队伍
那么肯定有一个队伍A的人数>=51人，也就是其他队伍的人数都比他少。
那么我们可以设置一个领地 x ，顺序让这些人去抢占领地，如果他们遇到同队的，就可以一起占领，如果不同队伍的，只能拼杀至死，去掉一人，那么到最后剩下的人一定是A队的人。
由此可得解法：
public int majorityElement(int[] nums) {
int x = nums[0]; //x为领地，先让第一个人占领
int count = 1;
for(int i = 1; i< nums.length ; i++){
//如果遇到同队伍的人，那么就一起占领
if(x == nums[i]){
count++;
} else if(count == 0) {
//如果已经无人占领了，那么就由当前的人来占领
count++;
x = nums[i];
} else {
//遇到不同队伍的人，拼杀减少一人
count--;
}
}
return x;
}太爱这个算法了，原来我们想的算法其实在生活中也没有那么复杂，都是简单且直接的
那么终于通过此算法得到了空间复杂度为O(1)的算法。
java工具类写法：
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}无言独上西楼，不再赘述。
注意
升级版：升级元素||
