原题链接在这里：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:
1 public class Solution { 2 public int majorityElement(int[] nums) { 3 /* 4 //Method 1, HashMap 5 HashMap<Integer, Integer> map = new HashMap<>(); 6 for(int i = 0;i<nums.length; i++){ 7 if(!map.containsKey(nums[i])){ 8 map.put(nums[i],1); 9 }else{ 10 map.put(nums[i],map.get(nums[i])+1); 11 } 12 } 13 14 Iterator<Integer> it = map.keySet().iterator(); //Iterate HashMap 15 while(it.hasNext()){ 16 int keyVal = it.next(); 17 //There is an error here: Pay attentation, it is ">", but not ">=" 18 //If we have three variables [3,2,3], ">=" will also return 2, 1>=3/2 19 if(map.get(keyVal) > nums.length/2){ 20 return keyVal; 21 } 22 } 23 24 return Integer.MIN_VALUE; 25 */ 26 27 /*Method 2, shortcut 28 Arrays.sort(nums); 29 return nums[nums.length/2]; 30 */ 31 32 //Method 3 33 if(nums == null || nums.length == 0) 34 return Integer.MAX_VALUE; 35 int res = nums[0]; 36 int count = 1; 37 for(int i = 1; i< nums.length; i++){ 38 if(res == nums[i]){ 39 count++; 40 }else if(count == 0){ 41 res = nums[i]; 42 count = 1; 43 }else{ 44 count--; 45 } 46 } 47 return res; 48 49 } 50 }