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

题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

代码如下：

package demo;

public class Test29 {
    public static int moreThanHalfNum(int[] numbers) {
        if (numbers == null || numbers.length < 1) {
            throw new IllegalArgumentException("array length must be larger than 0");
        }
        // 记录出现次数超过数组长度一半的数
        int result = numbers[0];
        // 记录次数
        int count = 1;
        // 从第2个数开始向后找
        for (int i = 1; i < numbers.length; i++) {
            // 如果计数为0
            if (count == 0) {
                // 重新记录一个数，假设它是出现次数超过数组长度一半的数
                result = numbers[i];
                // 记录次数
                count = 1;
            }
            // 如果记录的数与后面的数相等，则次数增加
            else if (result == numbers[i]) {
                count++;
            }
            // 如果不相等，则次数减少
            else {
                count--;
            }
        }

        // 计算result出现的次数
        int count2 = 0;
        for (int number : numbers) {
            if (result == number) {
                count2++;
            }
        }
        // 如果出现次数超过数组长度的一半，就返回该数
        if (count2 > numbers.length / 2) {
            return result;
        }
        // 否则就输入异常
        else {
            throw new IllegalArgumentException("invalid input");
        }
    }

    public static void main(String[] args) {
        System.out.println("存在出现次数超过数组长度一半的数字：");
        int[] numbers1 = { 1, 2, 3, 2, 2, 2, 5, 4, 2 };
        System.out.println(moreThanHalfNum(numbers1));
        System.out.println("存在出现次数超过数组长度一半的数字，且出现在数组前半部分：");
        int[] numbers2 = { 2, 2, 2, 2, 2, 1, 3, 4, 5 };
        System.out.println(moreThanHalfNum(numbers2));
        System.out.println("存在出现次数超过数组长度一半的数字，且出现在数组后半部分：");
        int[] numbers3 = { 1, 3, 4, 5, 2, 2, 2, 2, 2 };
        System.out.println(moreThanHalfNum(numbers3));
        System.out.println("只有1个数字：");
        int[] numbers4 = { 1 };
        System.out.println(moreThanHalfNum(numbers4));
        System.out.println();
        System.out.println();
        System.out.println("输入空指针：");
        System.out.println(moreThanHalfNum(null));
        System.out.println();
        System.out.println();
        System.out.println("不存在出现次数超过数组长度一半的数字：");
        int[] numbers5 = { 1, 2, 3, 2, 4, 2, 5, 2, 3 };
        System.out.println(moreThanHalfNum(numbers5));

    }
}

运行结果

来源：http://blog.csdn.net/derrantcm/article/details/46736859