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

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

方法一：基于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)