原题链接在这里：https://leetcode.com/problems/majority-element/
题目：
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
题解：
Method 1：最容易想到的就是用HashMap 计数，数值大于n/2(注意不是大于等于而是大于)，就是返回值。Time Complexity: O(n). Space: O(n).
Method 2: 用sort, 返回sort后array的中值即可. Time Complexity: O(n*logn). Space: O(1).
Method 3: 维护个最常出现值，遇到相同count++, 遇到不同count--, count为0时直接更改最常出现值为nums[i]. Time Complexity: O(n). Space: O(1).
AC Java:
public class Solution {
public int majorityElement(int[] nums) {
/*
//Method 1, HashMap
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0;i<nums.length; i++){
if(!map.containsKey(nums[i])){
map.put(nums[i],1);
}else{
map.put(nums[i],map.get(nums[i])+1);
}
}
Iterator<Integer> it = map.keySet().iterator(); //Iterate HashMap
while(it.hasNext()){
int keyVal = it.next();
//There is an error here: Pay attentation, it is ">", but not ">="
//If we have three variables [3,2,3], ">=" will also return 2, 1>=3/2
if(map.get(keyVal) > nums.length/2){
return keyVal;
}
}
return Integer.MIN_VALUE;
*/
/*Method 2, shortcut
Arrays.sort(nums);
return nums[nums.length/2];
*/
//Method 3
if(nums == null || nums.length == 0)
return Integer.MAX_VALUE;
int res = nums[0];
int count = 1;
for(int i = 1; i< nums.length; i++){
if(res == nums[i]){
count++;
}else if(count == 0){
res = nums[i];
count = 1;
}else{
count--;
}
}
return res;
}
}