majorityElement.java

import java.util.Arrays;
import java.util.HashMap;

/**
 * Created by xynophon on 15.2.27.
 */
public class majorityElement {
    public int majorityElement(int[] num) {
        //bad solution using Hash. O(n). it took 343ms.
        int half = num.length/2;
        int result = 0;
        HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
        for(int i = 0; i < num.length; i++){
            if(hm.containsKey(num[i])){
                int count = hm.get(num[i]);
                hm.put(num[i], count+1);
                if(count+1 > half){
                    result = num[i];
                }
            }else{
                hm.put(num[i], 1);
                if(half < 1)
                    result = num[i];
            }
        }

        
        // better solution using Array sort O(nlogn). it is smarter, faster. it took 244ms
        Arrays.sort(num);
        result = num[num.length/2];
        return result;
    }

    public static void main(String args[]){
//        int[] test = {1, 2, 2, 2, 3, 2, 1, 1, 2, 1, 3}; // 2 is expected
        int[] test = {6, 6, 6, 7, 7}; // 6 is expected.
        majorityElement me = new majorityElement();
        System.out.println(me.majorityElement(test));
    }
}