數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字。例如輸入一個長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)了5次，超過數(shù)組長度的一半，因此輸出2。如果不存在則輸出0。

以下稱這個數(shù)為H數(shù)

題目看上去很簡單，但這一題又一次的刷新了我的三觀。

想法1：

使用TreeMap<Integer,Integer>存儲記錄，Key是數(shù)字，Value是次數(shù)，TreeMap.get(TreeMap.lastKey()) 即為可能的H數(shù)。這里我對TreeMap理解有問題，TreeMap是基于Key進(jìn)行排序的，而不是Value。

想法2：

若H數(shù)存在，則H數(shù)必定是中位數(shù)。使用Arrays.sort(int[] array)對數(shù)組進(jìn)行排序，通過下標(biāo)獲取中位數(shù)。找到第一個與中位數(shù)相等的樹下標(biāo)index_begin，如果索引index_begin+len/2沒有越界，且其值等于中位數(shù)，則中位數(shù)即為H數(shù)，否則不存在；

    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
    }

最大復(fù)雜度來自Arrays.sort(array)為O(nlogn)

想法3：

先容我膜拜一下寫出這個方法的網(wǎng)友

因為H數(shù)大于一半，那么一個H數(shù)和一個非H數(shù)約去，最后一定剩下的一定為H數(shù)。

1. int num = array[i]，count=1 ，i++
2. 如果num == array[i] count++，否則count --，如果count = 0,則 num = array[i]，count =1，i++ 繼續(xù)執(zhí)行2
3. 若最后count > 0 num為可能的H數(shù)，否則不存在
4. 遍歷數(shù)字，驗證num 是否為H數(shù)

    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數(shù)
        for (int index : array) {
            if (index == num) count++;
        }
        if (count > array.length / 2) return num;
        else return 0;
    }

沒有循環(huán)嵌套，所以復(fù)雜度為O(n)。