给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于⌊ n/2 ⌋的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入:[3,2,3]
输出:3
示例 2:
输入:[2,2,1,1,1,2,2]
输出:2
Solution 1
常规解法，利用hashmap,当map中没有这个值时，放入map,并设value为1，有时，将值加一放入
class Solution {
public int majorityElement(int[] nums) {
Map<Integer,Integer> myMap = new HashMap();
int ret=0;
for (int num: nums) {
if (!myMap.containsKey(num))
myMap.put(num, 1);
else
myMap.put(num, myMap.get(num)+1);
if (myMap.get(num)>nums.length/2) {
ret = num;
break;
}
}
return ret;
}
}
O（n）时间，O（n）空间
Solution2
摩尔投票法，前提是它所找的数组中必定有众数
可以参考这个动画链接摩尔投票动画
public class Solution {
public int majorityElement(int[] num) {
int major=num[0], count = 1;
for(int i=0;i<num.length;i++){
if(count==0){
major = num[i];
count=1;
}else if(major==num[i]){
count++;
}else{
count--;
}
}
return major;
}
}
O（n）时间 O（1）空间
