//數(shù)組中出現(xiàn)次數(shù)超過一般的數(shù)字
public class MoreThanHalfNum {

// 判斷數(shù)組是否為空
public static boolean checkInvalidArray(int[] numbers) {
    if (numbers == null || numbers.length == 0)
        return true;
    return false;
}

// 基于快速排序算法的partition函數(shù)
public static int partition(int[] numbers, int left, int right) {
    int result = numbers[left];
    if (left > right) {
        return -1;
    }
    while (left < right) {
        while (left < right && numbers[right] >= result) {
            right--;
        }
        numbers[left] = numbers[right];
        while (left < right && numbers[left] < result) {
            left++;
        }
        numbers[right] = numbers[left];
    }
    numbers[left] = result;
    return left;
}

// 判斷中間的元素出現(xiàn)的次數(shù)是否超過數(shù)組長度的一半
public static boolean checkMoreThanHalf(int[] numbers, int length, int result) {
    int times = 0;
    for (int i = 0; i < length; i++) {
        if (numbers[i] == result) {
            times++;
        }
    }
    if (times * 2 > length)
        return true;
    return false;
}

// 找出數(shù)組的中位數(shù)，并放到中間位置 基于Partition函數(shù)的O(n)算法
public static int moreThanHalfNum(int[] numbers) {
    if (checkInvalidArray(numbers))
        return 0;
    int length = numbers.length;
    int middle = length / 2;
    int start = 0;
    int end = length - 1;
    int index = partition(numbers, start, end);
    while (index != middle) {
        if (index > middle) {
            end = index - 1;
            index = partition(numbers, start, end);
        } else {
            start = index + 1;
            index = partition(numbers, start, end);
        }

    }
    int result = numbers[middle];
    if (!checkMoreThanHalf(numbers, length, result)) {
        return 0;
    }
    return result;

}

// 根據(jù)數(shù)組特點(diǎn)求出O(n)的算法
public static int moreThanHalfNum2(int[] numbers) {
    if (checkInvalidArray(numbers))
        return 0;
    int result = numbers[0];
    int times = 1;
    for (int i = 1; i < numbers.length; i++) {
        if (times == 0) {
            result = numbers[i];
            times = 1;
        } else {
            if (numbers[i] == result) {
                times++;
            } else {
                times--;
            }
        }
    }
    if (!checkMoreThanHalf(numbers, numbers.length, result)) {
        return 0;
    }
    return result;
}

public static void main(String[] args) {
    int[] numbers = { 3, 3, 3, 3, 2, 2, 1 };
    System.out.println(moreThanHalfNum(numbers));
    System.out.println(moreThanHalfNum2(numbers));
}

}