题目：

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

三种解法：

1. 一次遍历，筛掉两个不同的数，其剩余数组中，频率超过一半的数还是超过一半…
2. 排序，选取中间的那个数，即是
3. 放到MAP中，选取频率最高的那个数

---

Python代码如下：

#!/usr/bin/env python
# coding=utf-8
import random

specified = 4;

# generate standard sample
def f(x):
    if x%2 == 0 or x%7 == 0: return specified
    return random.randint(1,100)
array = map(f, xrange(0,100))
#print array
#random.shuffle(array)
#print 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 temp

def 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) == specified
print findoutSpecifiedByMap(array) == specified
print findoutSpecifiedBySort(array) == specified

参考网址：

http://outofmemory.cn/