数组中出现次数超过一半的数字

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

    解题思路：数组中有一个数字出现的次数超过数组长度的一半，它出现的次数比其他所有数字出现的次数的和还要多。我们在遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次数。当遍历到下一个数字的时候，如果下一个数字和之前保存的数字相同，则次数加1；如果下一个数字和之前保存的数字不同，则次数减1。如果次数为0，保存下一个数字，并把次数设置为1。要找的数字肯定是最后一次把次数设为1时对应的数字。

    C#实现：

private static bool CheckInvalidArray(int[] numbers, int length)        {
            bool bInputInvalid = false;

            if (numbers == null || length <= 0)
                bInputInvalid = true;

            return bInputInvalid;
        }

        private static bool CheckMoreThanHalf(int[] numbers, int length, int number)
        {
            int times = 0;
            for (int i = 0; i < length; i++)
                if (numbers[i] == number)
                    times++;

            bool isMoreThanHalf = true;
            if (times * 2 <= length)
            {
                isMoreThanHalf = false;
            }

            return isMoreThanHalf;
        }

        public static int MoreThanHalfNum(int[] numbers, int length)
        {
            if (CheckInvalidArray(numbers, length))
                return 0;

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

            if (!CheckMoreThanHalf(numbers, length, result))
                result = 0;

            return result;
        }

    Java实现：

private static Boolean CheckInvalidArray(int[] numbers, int length) {Boolean bInputInvalid = false;if (numbers == null || length <= 0)bInputInvalid = true;return bInputInvalid;}private static Boolean CheckMoreThanHalf(int[] numbers, int length, int number) {int times = 0;for (int i = 0; i < length; i++)if (numbers[i] == number)times++;Boolean isMoreThanHalf = true;if (times * 2 <= length) {isMoreThanHalf = false;}return isMoreThanHalf;}public static int MoreThanHalfNum(int[] numbers, int length) {if (CheckInvalidArray(numbers, length))return 0;int result = numbers[0];int times = 1;for (int i = 1; i < length; i++) {if (times == 0) {result = numbers[i];times = 1;} else if (numbers[i] == result)times++;elsetimes--;}if (!CheckMoreThanHalf(numbers, length, result))result = 0;return result;}

    Python实现：

def check_invalid_array(numbers, length):    b_input_invalid = False    if numbers == None or length <= 0:        b_input_invalid = True    return b_input_invaliddef check_more_than_half(numbers, length, number):    times = 0    for item in numbers:        if item == number:            times += 1    is_more_than_half = True    if times *2 <= length:        is_more_than_half = False    return is_more_than_halfdef more_than_half_num(numbers, length):    if check_invalid_array(numbers, length):        return 0    result = numbers[0]    times = 1    for item in numbers:        if times == 0:            result = item            times = 1        elif item == result:            times += 1        else:            times -= 1    if not check_more_than_half(numbers, length, result):        result = 0    return result