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.

这道题我没有看提示，直接用hash表，遍历数组，将出现的次数保存到hash表中，最后遍历hash表，找出满足要求的元素。时间复杂度为O(n)

 1 import java.util.Hashtable;
 2 import java.util.Iterator;
 3 
 4 public class Solution {
 5     public int majorityElement(int[] num) {
 6         Hashtable<Integer, Integer> hashtable = new Hashtable<Integer, Integer>();
 7         int result = 0;
 8         
 9         for(int i = 0; i < num.length; i++){
10             Integer times = hashtable.get(num[i]);
11             if(times == null)
12                 hashtable.put(num[i], 1);
13             else{
14                 times = times + 1;
15                 hashtable.put(num[i], times);
16             }
17         }//for
18         //遍历hash表
19         Iterator<Integer> it = hashtable.keySet().iterator();
20         while(it.hasNext()){
21             int key = it.next();
22             if(hashtable.get(key) > num.length / 2){
23                 result = key;
24                 break;
25             }
26         }
27         
28         return result;
29     }
30 }