Java 實作數組中出現次數超過一半的數字

數組中有一個數字出現的次數超過數組長度的一半，請找出這個數字。

比如輸入一個長度為9的數組｛1，2，3，2。2，2。5，4，2｝。因為數字2在數組中出現5次，超過數組長度的一半，是以輸出2.

代碼

公共代碼

/**
     * 快排
     * @param array
     * @param lo
     * @param hi
     */
    public static void sort(int[] array,int lo ,int hi){
        if(lo>=hi){
            return ;
        }
        int index=partition(array,lo,hi);
        sort(array,lo,index-1);
        sort(array,index+1,hi);
    }

    public static int partition(int []array,int start,int end){
        // 固定的切分方式
        int key = array[start];
        while(start < end){
            // 從後半部分向前掃描
            while(end > start && array[end] >= key){
                end--;
            }
            array[start] = array[end];
            // 從前半部分向後掃描
            while(start < end && array[start] < key){
                start++;
            }
            array[end]=array[start];
        }
        array[start]=key;
        return end;
    }
           

解法一

因為是數組，并且出現次數超過數組長度一半，對數組排序，那麼排序後的數組的中位數應該就是要找的數字。是以先采用快速排序使數組有序，然後驗證中位數是否滿足條件。

private static Integer findMoreThanHalf1(int[] array) {
        if (array == null || array.length == 0) {
            return null;
        }
        int length = array.length;
        int middle = length >> 1;
        // 實際開發中，誰會自己寫排序啊，直接用現成的就OK了
        // Arrays.sort(array)
        sort(array, 0, length - 1);
        int result = array[middle];
        if (!isExist(array, result)) {
            return null;
        }
        return result;
    }
           

解法二

一個元素出現的次數超過一半，也就是說，其他元素出現次數之和也沒有該元素多，即 count(target) - count(others) > 0，是以比較前後兩個數，相等 + 1，不相等 - 1，當為0時更新記錄的數字，周遊一遍後，如果存在這樣的數字，計數器應 > 0，此時記錄的數字就是要找的數字。

public static Integer findMoreThanHalf2(int[] array) {
        if (array == null || array.length == 0) {
            return null;
        }
        // 初始化結果result及用于計數的count
        int result = array[0];
        int count = 1;
        for (int i = 1; i < array.length; i++) {
            if (array[i] == result) {
                // 如果相等，則計數器+1
                count++;
            } else {
                // 如果不相等，則計數器-1
                count--;
            }
            if (count == 0) {
                // 如果此時count為0，更新result值
                result = array[i];
                count = 1;
            }
        }
        // 1. 計數器等于0時，說明不存在，因為是大于數組長度的一半，是以不考慮等于一半的情況
        // 2. 計數器大于0時，再次驗證該數字的出現次數是否真的大于數組長度的一半
        if (count == 0 && !isExist(array, result)) {
            return null;
        }

        return result;
    }