## 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


# -*- 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