两种方法
数组中出现次数超过一半的数字
http://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163
快速排序思想：
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
def partition(num, start, end):
pivot = start
index = start + 1
i = index
while i <= end:
if num[i] <= num[pivot]:
num[index], num[i] = num[i], num[index]
index += 1
i += 1
num[pivot], num[index-1] = num[index-1], num[pivot]
return index-1
if len(numbers) == 0:
return 0
start = 0
end = len(numbers) - 1
mid = end // 2
index = partition(numbers, start, end)
while index != mid:
if index > mid:
end = index - 1
index = partition(numbers, start, end)
else:
start = index + 1
index = partition(numbers, start, end)
count = 0
for i in numbers:
if i == numbers[index]:
count += 1
if count*2 <= len(numbers):
return 0
return numbers[index]投票法
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
temp = numbers[0]
count = 1
for i in range(1, len(numbers)):
if temp == numbers[i]:
count += 1
else:
count -= 1
if count == 0:
temp = numbers[i]
count = 1
count = 0
for i in numbers:
if i == temp:
count += 1
if count*2 <= len(numbers):
return 0
return temp