剑指Offer第39题——数组中出现次数超过一半的数

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

可以先排序，排序之后，出现次数超过一半的数字肯定出现在中位数的位置，如果不考虑时间复杂度，可以将数组排序，然后取中间位置的数字。

public int MoreThanHalfNum_Solution(int [] array) {
       if (array == null || array.length == 0)
           return 0;
       Arrays.sort(array);
       int count = 0;
       int v = array[array.length / 2];
       for (int i : array) {
           if(i == v){
               count++;
           }
       }
       // 判断出现的次数到底是不是大于长度的一半 
       return count>array.length/2?v:0;
       
   }

但事实情况为必须要考虑时间复杂度，sort方法的时间复杂度为O(nlgn)，复杂度太高。可以使用其他方法。
使用快速排序的切分法可以有效降低时间复杂度。时间复杂度为O(n)

    // 主方法
    public int moreThanHalfNum(int[] array) {
        if (array == null || array.length == 0)
            return 0;

        int mid = select(array, array.length / 2);
        return checkMoreThanHalf(array, mid);
    }
    /**
     * 快速排序的切分方法
     */
    private int partition(int[] array, int low, int high) {
        int i = low;
        int j = high + 1;
        int v = array[low];
        while (true) {
            // 拿low+1之后的与low比较，找到比low大的
            while (array[++i] < v) {
                // 左侧指针指到了最右侧
                if (i == high)
                    break;
            }
            // 拿high之前的与low比较，找到比low小的
            while (array[--j] > v) {
                // 右侧指针指到了最左侧
                if (j == low)
                    break;
            }
            // 两个指针相遇
            if (i >= j) {
                break;
            }
            // 交换i与j的位置，相当于按照大小调换
            swap(array, i, j);
        }
        // 跳出循环证明已经将小的移到了左边，大的移到了右边，交换low与j的位置，实现low的位置正确
        swap(array, low, j);
        return j;
    }
    /**
     * 选择排名为k的元素,只是部分排序，时间复杂度为O(N)
     */
    private int select(int[] array, int k) {
        int low = 0;
        int high = array.length - 1;
        // high==low时只有一个元素，不切分
        while (high > low) {
            int j = partition(array, low, high);
            // 如果j==k，说明找到了排名为k的元素，即为array[j]
            if (j == k)
                return array[k];
            // 如果j>k，说明找到的这个数的顺序太靠后，j后面都是比k大的，需要往前找，类似于二分法
            else if (j > k)
                high = j - 1;
            // 如果j<k，说明找到的这个数的顺序太靠前，j前面都是比k小的，需要往后找，类似于二分法
            else if (j < k)
                low = j + 1;
        }

        return array[k];
    }
    /**
     * 统计中位数是否超过数组元素个数的一半，若没有默认返回0
     */
    private int checkMoreThanHalf(int[] array, int number) {
        int count = 0;
        for (int a : array) {
            if (a == number)
                count++;
        }

        return count > array.length / 2 ? number : 0;
    }