【Java】majorityElement，

【Java】majorityElement，

/**
 * Created on 16/6/4.
 */
import java.util.Arrays;
import java.util.HashMap;
public class majorityElement {
    public static void main(String[] args) {
        int[] x = {1,2,4,4,4,3};
        System.out.println(majorityElement(x));
        System.out.println(anotherMajorityElement(x));
        System.out.println(thirdMajorityElement(x));
    }

    public static int majorityElement(int[] x) {
        Arrays.sort(x);
        return x[x.length/2];
    }

    public static int anotherMajorityElement(int[] x) {
        if (x == null || x.length == 0) {
            return 0;
        }
        int major = x[0];
        int count = 1;
        for (int i = 1; i < x.length; i++) {
            if (major == x[i]) {
                count++;
            } else {
                count--;
            }
            if (count == 0) {
                major = x[i];
                count = 1;
            }
        }
        return major;
    }

    public static int thirdMajorityElement(int[] x) {
        int len = x.length;
        if (len < 3) {
            return x[0];
        }
        int m = (len % 2 == 0) ? len / 2 : len / 2 + 1;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int key : x) {
            if (!map.containsKey(key)) {
                map.put(key, 1);
            } else {
                int count = map.get(key);
                if (count + 1 > m) {
                    return key;
                }
                map.put(key, count + 1);
            }
        }
        return 0;
    }
}