寻找数组中出现次数≥N/3的元素（不使用Moore算法）

方法1：哈希表统计法 #

这是最直观的解法，通过统计每个元素的出现次数筛选目标元素：

• 遍历数组，用哈希表记录每个元素的出现次数
• 遍历哈希表，收集所有出现次数≥len(arr)/3的元素

Python代码示例：

def find_majority_elements(arr):
    count = {}
    n = len(arr)
    threshold = n / 3
    for num in arr:
        count[num] = count.get(num, 0) + 1
    return [num for num, cnt in count.items() if cnt >= threshold]

• 时间复杂度：O(n)，两次线性遍历
• 空间复杂度：O(n)，最坏情况存储所有不同元素

方法2：排序后遍历 #

排序后相同元素会连续排列，通过遍历统计连续元素的出现次数：

• 对数组进行原地排序
• 遍历排序后的数组，维护当前元素的计数，当计数≥n/3时将元素加入结果集（避免重复添加同一元素）

Python代码示例：

def find_majority_elements(arr):
    arr.sort()
    n = len(arr)
    threshold = n / 3
    result = []
    count = 1
    for i in range(1, n):
        if arr[i] == arr[i-1]:
            count += 1
        else:
            if count >= threshold:
                result.append(arr[i-1])
            count = 1
    # 检查最后一组连续元素
    if count >= threshold:
        result.append(arr[-1])
    return list(set(result))

• 时间复杂度：O(n log n)，主要由排序操作决定
• 空间复杂度：O(1)（忽略排序栈空间，使用原地排序算法）

方法3：分治法 #

将问题拆解为子问题，合并结果后验证：

• 将数组分成左右两个子数组，分别找出子数组中符合条件的元素
• 合并子问题的结果，统计候选元素在整个数组中的出现次数，判断是否满足≥n/3的条件
• 最终收集所有符合条件的元素

Python代码示例：

def count_element(arr, num):
    return arr.count(num)

def find_majority_recursive(arr, left, right):
    if left == right:
        return [arr[left]]
    mid = (left + right) // 2
    left_maj = find_majority_recursive(arr, left, mid)
    right_maj = find_majority_recursive(arr, mid+1, right)
    # 合并候选元素并去重
    candidates = list(set(left_maj + right_maj))
    n = right - left + 1
    threshold = n / 3
    result = []
    for num in candidates:
        if count_element(arr[left:right+1], num) >= threshold:
            result.append(num)
    return result

def find_majority_elements(arr):
    if not arr:
        return []
    return list(set(find_majority_recursive(arr, 0, len(arr)-1)))

• 时间复杂度：O(n log n)，递归拆分+线性统计
• 空间复杂度：O(log n)，递归调用栈深度

内容的提问来源于stack exchange，提问作者YOGENDRA SINGH