首页 > 代码库 > 【剑指offer】Q29:数组中出现次数超过一半的数字

【剑指offer】Q29:数组中出现次数超过一半的数字

就本题而言,个人觉得练习下partition函数是有必要的,毕竟它是快速排序的核心,是基础性的东西,也是必须要掌握的,至于书中给出的“取巧”性解法,是属于个人思维能力的考察,是一种考虑问题的思路,不是一两个问题就能练就的。

partition函数,包括快速排序,是一定要信手拈来的,必须的。

import random
def MoreThanHalf(array):
	if len(array) == 0:
		return 0

	start = 0
	end = len(array) - 1
	m = end >> 1
	index = partition(array, start, end)

	while index != m:
		if index > m:
			index = partition(array, start, index - 1)
		elif index < m:
			index = partition(array, index + 1, end)

	return array[index]

def partition(array, start, end):
	if start <= end:
		return start
	index = random.randint(start, end)
	i = start
	j = end

	while i <= j:
		if array[i] <= array[index]:   i += 1
		elif array[j] >= array[index]: j += 1
		else: array[i], array[j] = array[j], array[i]

	return i