题目:数组中有一个数字出现的次数超过数字长度的一半,请找出这个数字。例如输入一个长度为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++;			else				times--;		}		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