剑指Offer-28 数组中超过一半的数

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

以下称这个数为H数

题目看上去很简单，但这一题又一次的刷新了我的三观。

想法1：

使用TreeMap<Integer,Integer>存储记录，Key是数字，Value是次数，TreeMap.get(TreeMap.lastKey()) 即为可能的H数。这里我对TreeMap理解有问题，TreeMap是基于Key进行排序的，而不是Value。

想法2：

若H数存在，则H数必定是中位数。使用Arrays.sort(int[] array)对数组进行排序，通过下标获取中位数。找到第一个与中位数相等的树下标index_begin，如果索引index_begin+len/2没有越界，且其值等于中位数，则中位数即为H数，否则不存在；

    public int MoreThanHalfNum_Solution(int[] array) {
        Arrays.sort(array); // sort nlogn
        int len = array.length;
        int avg = array[len / 2]; //if len=3 avg_index = 1, len=4 avg_index = 1,2
        int begin = -1;
        int end = -1;
        for (int i = len / 2; ; i--) {
            if (i < 0 || array[i] != avg) {
                begin = i + 1;
                break;
            }
        }// search from half
        end = begin + len / 2;// end index
        if (end < len && array[end] == avg) return avg; // H.num > len/2
        else return 0;// No H
    }

最大复杂度来自Arrays.sort(array)为O(nlogn)

想法3：

先容我膜拜一下写出这个方法的网友

因为H数大于一半，那么一个H数和一个非H数约去，最后一定剩下的一定为H数。

1. int num = array[i]，count=1 ，i++
2. 如果num == array[i] count++，否则count --，如果count = 0,则 num = array[i]，count =1，i++ 继续执行2
3. 若最后count > 0 num为可能的H数，否则不存在
4. 遍历数字，验证num 是否为H数

    public int MoreThanHalfNum_Solution2(int[] array) {
        int num = array[0]; 
        int count = 1;
        for (int i = 1; i < array.length; i++) {
            if (array[i] == num) {
                count++;
            } else {
                count--;
                if (count == 0) {
                    num = array[i];
                    count = 1;
                }
            }
        }
        if (count == 0) return 0;
        count = 0;
        
        // 检验Num是否为H数
        for (int index : array) {
            if (index == num) count++;
        }
        if (count > array.length / 2) return num;
        else return 0;
    }

没有循环嵌套，所以复杂度为O(n)。