Python实现查找数组中超过一半的元素

在给定的数组中，存在一个元素其出现的频率超过了数组长度的一半。本篇文章将探讨如何有效地识别这一特殊元素。我们将从三种不同的角度出发，分别是直接计数法、哈希表（字典）法和基于排序的方法。

直接计数法

此方法适用于不考虑时间复杂度的情况下。基本思路是遍历数组中的每个元素，并使用 Python 列表的 count() 方法来计算该元素在数组中出现的次数。如果某个元素的出现次数大于数组长度的一半，则返回该元素。

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

哈希表法

为了提高效率，可以使用哈希表（即 Python 中的字典）来存储每个元素及其对应的出现次数。遍历数组时更新字典，之后再次遍历字典以确定是否有任何元素的出现次数超过了一半。这种方法的时间复杂度接近 O(n)，其中 n 是数组的长度。

def more_than_half_num(arr):
    count_dict = {}
    for num in arr:
        if num in count_dict:
            count_dict[num] += 1
        else:
            count_dict[num] = 1
    half = len(arr) // 2
    for key, value in count_dict.items():
        if value > half:
            return key
    return None

排序法

由于目标元素在数组中出现的次数超过一半，那么它必定位于排序后数组的中点位置。首先对数组进行排序，然后检查位于中间位置的元素是否满足条件。这里我们使用快速排序作为示例来展示整个过程。

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

def partition(arr, left, right):
    pivot = arr[right]
    i = left - 1
    for j in range(left, right):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[right] = arr[right], arr[i + 1]
    return i + 1

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

单次遍历法

考虑到目标元素出现的频率超过数组中其他所有元素的总和，可以设计一种线性时间复杂度的方法。该方法通过维护两个变量——当前候选者和计数器，在遍历数组的过程中动态调整这两个变量。当遇到与当前候选者相同的元素时增加计数器；反之减少计数器。一旦计数器归零，则更换新的候选者并将计数器重置为1。最后再验证最终的候选者是否确实满足条件。

def more_than_half_num(arr):
    candidate = arr[0]
    count = 1
    for num in arr[1:]:
        if num == candidate:
            count += 1
        else:
            count -= 1
        if count == 0:
            candidate = num
            count = 1
    if arr.count(candidate) > len(arr) // 2:
        return candidate
    return None