给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
解析：
题目咋一看感觉稳了有木有，解题思路出奇的清晰啊：构造一个hash存储结构，将数组中元素值作为key，该元素出现的次数作为value存放在hash中，遍历hash找出第一个value大于n/2的key返回即可。
public static int majorityElement(int[] nums) {
Map<Integer, Integer> hash = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
Integer temp = null;
hash.put(nums[i], null != (temp = hash.get(nums[i]))?++temp:1);
}
for (Integer in : hash.keySet()) {
if (hash.get(in) > (nums.length/2)) {
return in;
}
}
return 0;
}
可以看出如上思路的代码实现时间复杂度O(n),空间复杂度也为O(n)。
那么，问题来了，有没有更高效（无论从时间上和空间上）的方式来解决这个问题呢？
答案是有的，采用摩尔投票法，其算法思想为：将数组中的第一个数假设为众数，然后进行统计其出现的次数，如果遇到同样的数，则计数器自增1，否则计数器自减1，如果计数器减到了0，则更换下一个数字为候选者。
public static int majorityElement1(int[] nums) {
//假设第一个节点为目标节点
int temp = nums[0];
int count = 1;
for (int i = 1; i < nums.length; i++) {
//若上次循环累积次数为零，则更新当前节点为目标节点并设累计次数为1
if (0 == count) {
temp = nums[i];
count = 1;
}else {
//否则累加或者累减
if (nums[i] == temp) {
count++;
}else {
count--;
}
}
}
return temp;
}
可见此实现的时间复杂度为O(n)，而空间复杂度则缩减为了O(1)。
