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.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
1 public class Solution { 2 public int majorityElement(int[] num) { 3 int length=num.length; 4 if (length==1) { 5 return num[0]; 6 } 7 HashMap<Integer, Integer> map =new HashMap<>(); 8 for (int i = 0; i < length; i++) { 9 if (!map.containsKey(num[i])) { 10 map.put(num[i], 1); 11 }else { 12 int value=map.get(num[i])+1; 13 if (value>length/2) { 14 return num[i]; 15 }else { 16 map.put(num[i], value); 17 } 18 19 20 } 21 } 22 return 0; 23 } 24 }
原文：http://www.cnblogs.com/birdhack/p/4178933.html