題目：數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半谱净，請(qǐng)找出這個(gè)數(shù)字。
方法一：基于Partition函數(shù)的O(n)算法
數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)了數(shù)組長(zhǎng)度的一半亭姥，那么這個(gè)數(shù)一定是這個(gè)數(shù)組的中位數(shù)三圆。我們需要找到這個(gè)數(shù)組的第n/2大的數(shù)字。所以問(wèn)題轉(zhuǎn)化成找數(shù)組中第k大的數(shù)這樣的問(wèn)題蒜绽。
跟快速排序的Partition函數(shù)一樣，我們隨機(jī)選擇數(shù)組中的一個(gè)數(shù)字桶现，調(diào)整數(shù)組中數(shù)字的順序躲雅，使得比選中數(shù)字小的都在它的左邊，其它的都在它右邊骡和。如果這個(gè)選中的數(shù)字的下標(biāo)剛好是n/2相赁，那么這個(gè)數(shù)字就是數(shù)組中的中位數(shù)。如果它的下標(biāo)大于n/2慰于，那么中位數(shù)應(yīng)該位于它的左邊钮科，如果它的下標(biāo)小于n/2，那么中位數(shù)位于它的右邊婆赠。
方法二：
在遍歷數(shù)組的時(shí)候保存兩個(gè)值：一個(gè)是數(shù)組中的一個(gè)數(shù)字绵脯，一個(gè)是次數(shù)。當(dāng)遍歷下一個(gè)數(shù)字的時(shí)候，如果上一個(gè)數(shù)字和之前保存的數(shù)字相同桨嫁，則次數(shù)加1，如果不同份帐，則次數(shù)減1璃吧。如果次數(shù)為零，則需要保存下一個(gè)數(shù)字废境，并把次數(shù)設(shè)為1畜挨。
下面的Python代碼分別實(shí)現(xiàn)了上面兩種方法：
#encoding=utf8
'''
題目：數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半，找出這個(gè)數(shù)字
'''
def partition(num_list, start, end):
'''將num_list從start開(kāi)始噩凹，到end結(jié)束的部分分組巴元，以start位置的數(shù)字為基準(zhǔn)，返回基準(zhǔn)最后所在的位置'''
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中間的數(shù)字'''
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)
