数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
Solutions
第一种解法是最简单的方式，也就是将数组排序，取中间那个数，可以去计数判断是否超过半数。
# -*- coding:utf-8 -*-
class Solution:
def partition(self, arr, low, high):
pivot = arr[high]
i = low
for j in xrange(low, high):
if arr[j] <= pivot:
arr[j], arr[i] = arr[i], arr[j]
i += 1
arr[i], arr[high] = arr[high], arr[i]
return i
def quick_sort(self, arr, low=0, high=None):
if high is None:
high = len(arr) - 1
def _quicksort(arr, low, high):
if low >= high:
return
pivot = self.partition(arr, low, high)
_quicksort(arr, low, pivot-1)
_quicksort(arr, pivot+1, high)
return _quicksort(arr, low, high)
def MoreThanHalfNum_Solution(self, numbers):
# write code here
if not numbers:
return 0
self.quick_sort(numbers)
mid = numbers[len(numbers)/2]
count = 0
for num in numbers:
if num == mid:
count += 1
if count > len(numbers)/2:
return mid
else:
return 0
第二种方法是通过这种需求的特点，满足要求的数组中的那个数的个数很定是比数组中其他所有数的个数加起来都多，那么我们就用一种方式利用起这个不等式。从前往后遍历时，如果当前数字跟前一个相同，我们就在计数上加 1，否则就减 1，当计数为零时，我们重新还数统计，总的来说满足需求的数，会在几次重新登榜之后最后落实。
# -*- coding:utf-8 -*-
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
# write code here
if not numbers:
return 0
res = None
count = 0
for num in numbers:
if count == 0:
res = num
count += 1
elif num == res:
count += 1
else:
count -= 1
if count > 0:
times = 0
for num in numbers:
if num == res:
times += 1
if times * 2 <= len(numbers):
res = 0
return res
else:
return 0