【剑指Offer】数组中出现次数超过一半的数字

题目

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

基于Partition函数的O(n)算法

public int MoreThanHalfNum_Solution(int[] array) {
    if (array == null || array.length <= 0)
        return 0;

    int left = 0;
    int right = array.length - 1;
    int middle = (left + right) / 2;

    int pivot = Partition(array, left, right);

    while (pivot != middle) {
        if (pivot < middle) {
            left = pivot + 1;
            pivot = Partition(array, left, right);
        } else {
            right = pivot - 1;
            pivot = Partition(array, left, right);
        }
    }

    int result = array[middle];

    if (!CheckMoreThanHalf(array, result))
        return 0;

    return result;
}

private int Partition(int[] array, int start, int end){
    int i = start + 1;

    for (int j = start + 1; j <= end; j++){
        if (array[j] < array[start]) {
            Swap(array, i, j);
            i++;
        }
    }

    Swap(array, start, --i);

    return i;
}

private void Swap(int[] array, int i, int j){
    if (i == j)
        return;

    array[i] = array[i] ^ array[j];
    array[j] = array[i] ^ array[j];
    array[i] = array[j] ^ array[i];
}

private boolean CheckMoreThanHalf(int[] array, int result) {
    int count = 0;

    for (int i = 0; i < array.length; i++) {
        if (result == array[i])
            count++;
    }

    if (2 * count <= array.length)
        return false;

    return true;
}

根据数组特点找出O(n)的算法

public int MoreThanHalfNum_Solution(int[] array) {
    if (array == null || array.length <= 0)
        return 0;

    int result = array[0];
    int count = 1;

    for (int i = 1; i < array.length; i++) {
        if (count == 0) {
            count = 1;
            result = array[i];
        }
        else if (array[i] == result)
            count++;
        else
            count--;
    }

    if (!CheckMoreThanHalf(array, result))
        return 0;

    return result;
}

private boolean CheckMoreThanHalf(int[] array, int result) {
    int count = 0;

    for (int i = 0; i < array.length; i++) {
        if (result == array[i])
            count++;
    }

    if (2 * count <= array.length)
        return false;

    return true;
}