找出数组中出现频率超过一半的数，数组超过一半,有一个乱序的数组，其中有

找出数组中出现频率超过一半的数，数组超过一半,有一个乱序的数组，其中有

有一个乱序的数组，其中有一个数占了一半以上，找出这个数

三种方法： 1.一次遍历，筛掉两个不同的数，其剩余数组中，频率超过一半的数还是超过一半...

2.排序， 选取中间的那个数，即是

3.放到MAP中，选取频率最高的那个数

import randomspecified = 4;# generate standard sampledef f(x):    if x%2 == 0 or x%7 == 0:return specified    return random.randint(1,100)array = map(f, xrange(0,100))#random.shuffle(array)#print array.count(specified)# findout the value , Tree method to solve the question:def findoutSpecifiedByIterOnce(array):    temp = array[0]    count = 1    for i in xrange(1, len(array)):        if count == 0:            temp = array[i]            count += 1            continue        if temp == array[i]:            count += 1        else:            count -= 1    #print "show ", temp    return tempdef findoutSpecifiedBySort(array):    array.sort()    return array[len(array)/2]def findoutSpecifiedByMap(array):    arrayCountMap = {x : array.count(x) for x in set(array)}    return sorted(arrayCountMap.items(), key=lambda arrayCountMap:arrayCountMap[1], reverse=True)[0][0]print findoutSpecifiedByIterOnce(array) == specifiedprint findoutSpecifiedByMap(array) == specifiedprint findoutSpecifiedBySort(array) == specified#该片段来自于http://byrx.net