169. Majority Element Java Solutin

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.

Subscribe to see which companies asked this question

 1 public class Solution {
 2     public int majorityElement(int[] nums) {
 3         if(nums == null) return 0;
 4         Map<Integer,Integer> hm = new HashMap<Integer ,Integer>();
 5         for(int i= 0;i< nums.length;i++){
 6             if(hm.containsKey(nums[i])) hm.put(nums[i],hm.get(nums[i]) + 1);
 7             else{
 8                 hm.put(nums[i],1);
 9             }
10         }
11         int halflen = nums.length/2;
12         int res = 0;
13         for(int key : hm.keySet()){
14             if(hm.get(key) > halflen){
15                 res = key;
16                 break;
17             }
18         }
19         return res;
20     }
21 }

方法2：排序后，取中间的元素就是所求值。

方法3：转自：http://blog.csdn.net/feliciafay/article/details/45006661

从头到尾扫描一遍数组，记录当前的majority element的count。

 1 // 259ms
 2 public class Solution {
 3     public int majorityElement(int[] num) {
 4         if(num.length < 3) return num[0];
 5         int majority = num[0];
 6         int count = 1;
 7         //1,1,1,1,2,1,3,1,2,2,2,2,2,2,
 8         for (int i = 1; i < num.length; ++i) {
 9             if (count == 0) {
10                 majority = num[i];
11                 ++count;
12             } else if (num[i] == majority)  {
13                 ++count;
14             } else {
15                 --count;
16             }
17         }
18         return majority;
19     }
20 }