一个整型数组中有一半以上的数是相同的,如何找到这个数

Question

一个整型数组中有一半以上的数是相同的,如何找到这个数? 用效率最高的方法,  Arrays.sort(a,0,a.length);

Answer 1

目前我的代码是这样的
int a[] = { 1, 2, 3, 5, 6, 2, 2, 2 };
for (int i = 0; i < a.length; i++) {
Arrays.sort(a, 0, a.length);
System.out.println(a[i]);
}
我先排完序了就是不知道该怎样获取2.

Answer 2

其实如果是我的话，根本不排序。直接建立一个HashMap<Integer, Integer>然后for(int i=0; i<a.length; i++) {
  key就是i，value就是出现次数
  某次检查发现value >= a.length，就说明已经找到了
}

Answer 3

为性能考虑，可以做一个内部类，避免每次计数都要创建Integer对象，类似于：    private static class Counter {
        private int cnt;
        public Counter inc() {
            cnt++;
            return this;
        }
        public int value() {
            return cnt;
        }
        public String toString() {
            return String.valueOf(cnt);
        }
    }
这样循环可以简化：        Map<Integer, Counter> mapCounter = new HashMap<Integer, Counter>();
        for (int i = 0; i < a.length; i++) {
            Counter cnt = mapCounter.get(a[i]);
            if (cnt == null) {
                cnt = new Counter();
                mapCounter.put(words[i], cnt.inc());
            } else {
                cnt.inc();
                if (cnt.value() >= a.length / 2) break; // 找到了
            }
        }