找出数组中出现次数超过一半的数

面试遇到的题目，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

计数+比较

不考虑效率，采用最简单的办法，遍历数组，使用 List 的 count() 方法统计元素出现的次数：

def more_than_half_num(arr):
    half = len(arr) // 2
    for i in arr:
        if arr.count(i) > half:
            return i
    return None

构造一个map，key为元素的值，value为元素出现的次数，然后遍历map找到目标元素：

def more_than_half_num(arr):
    dict = {}
    for i in arr:
        if i in dict:
            dict[i] += 1
        else:
            dict[i] = 1

    half = len(arr) // 2
    for k, v in dict.items():
        if v > half:
            return k
    return None

排序+中位数

数组 排序 后，如果符合条件的数存在，则一定是数组中间那个数。可使用 排序算法 对数组进行排序，然后求排序后数组的中间数 + 判断中间数出现次数是否超过数组的一半。下面以快速排序为例：

def part_sort(arr, left, right):
    key = right
    while left < right:
        while left < right and arr[left] <= arr[key]:
            left += 1
        while left < right and arr[right] >= arr[key]:
            right -= 1
        arr[left], arr[right] = arr[right], arr[left]
        print(arr)
    arr[left], arr[key] = arr[key], arr[left]
    return left


def quick_sort(arr, left, right):
    if left >= right:
        return
    index = part_sort(arr, left, right)
    quick_sort(arr, left, index - 1)
    quick_sort(arr, index, right)


def more_than_half_num(arr):
    length = len(arr)
    quick_sort(arr, 0, length - 1)
    res = arr[length // 2]
    if arr.count(res) > length // 2:
        return res
    else:
    	return None

一次遍历

数组中有一个数字出现的次数超过数组长度的一半，也就是说出现的次数比其他所有数字出现次数的和还要多。因此我们可以考虑在遍历数组的时候利用两个辅助变量，一个记录数字出现的次数，一个记录数字。

• 当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；
• 如果下一个数字和我们之前保存的数字不同，则次数减1。
• 如果次数为零，我们需要保存下一个数字，并把次数设为1。

def more_than_half_num(arr):
    res = arr[0]
    cnt = 1
    for i in range(1, len(arr)):
        if arr[i] == res:
            cnt += 1
        else:
            cnt -= 1
        if cnt == 0:
            res = arr[i]
            cnt = 1
    if arr.count(res) > len(arr)//2:
        return res
    else:
        return None