//数组中出现次数超过一般的数字
public class MoreThanHalfNum {

// 判断数组是否为空
public static boolean checkInvalidArray(int[] numbers) {
    if (numbers == null || numbers.length == 0)
        return true;
    return false;
}

// 基于快速排序算法的partition函数
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;
}

// 判断中间的元素出现的次数是否超过数组长度的一半
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;
}

// 找出数组的中位数，并放到中间位置 基于Partition函数的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;

}

// 根据数组特点求出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));
}

}