题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
方法一：基于Partition函数的O(n)算法
数组中有一个数字出现的次数超过了数组长度的一半，那么这个数一定是这个数组的中位数。我们需要找到这个数组的第n/2大的数字。所以问题转化成找数组中第k大的数这样的问题。
跟快速排序的Partition函数一样，我们随机选择数组中的一个数字，调整数组中数字的顺序，使得比选中数字小的都在它的左边，其它的都在它右边。如果这个选中的数字的下标刚好是n/2，那么这个数字就是数组中的中位数。如果它的下标大于n/2，那么中位数应该位于它的左边，如果它的下标小于n/2，那么中位数位于它的右边。
方法二：
在遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次数。当遍历下一个数字的时候，如果上一个数字和之前保存的数字相同，则次数加1，如果不同，则次数减1。如果次数为零，则需要保存下一个数字，并把次数设为1。
下面的Python代码分别实现了上面两种方法：
#encoding=utf8
'''
题目：数组中有一个数字出现的次数超过数组长度的一半，找出这个数字
'''
def partition(num_list, start, end):
'''将num_list从start开始，到end结束的部分分组，以start位置的数字为基准，返回基准最后所在的位置'''
pivot = num_list[start]
while start < end:
while start < end and num_list[end] >= pivot:end -= 1
if start < end:num_list[start] = num_list[end]
while start < end and num_list[start] <= pivot:start += 1
if start < end:num_list[end] = num_list[start]
num_list[start] = pivot
return start
def find_half_num_1(num_list):
'''返回num_list中间的数字'''
if type(num_list) != type([]) or len(num_list) == 0:
return None
start = 0
end = len(num_list) - 1
middle = end / 2
index = partition(num_list, start, end)
while index != middle:
if index > middle:
end = index - 1
index = partition(num_list, start, end)
else:
start = index + 1
index = partition(num_list, start, end)
return num_list[middle]
def find_half_num_2(num_list):
if type(num_list) != type([]):
return None
result = None
time = 0
for i in range(0, len(num_list)):
if time == 0:
result = num_list[i]
time = 1
else:
if num_list[i] == result:
time += 1
else:
time -= 1
return result
if __name__ == '__main__':
l_1 = [1,2,3,4,5,6,7,8,2,2,2,2,2,2,2,2,2,2,2,2]
l_2 = []
l_3 = [1,2,3,4,5,6,7,8,9,9,9,9,9,9,9,9,9,9,9,9]
l_4 = None
l_5 = [5]
print find_half_num_1(l_1)
print find_half_num_1(l_2)
print find_half_num_1(l_3)
print find_half_num_1(l_4)
print find_half_num_1(l_5)
print find_half_num_2(l_1)
print find_half_num_2(l_2)
print find_half_num_2(l_3)
print find_half_num_2(l_4)
print find_half_num_2(l_5)
