28 数组中出现次数超过一半的数字

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例：

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

解题思路

方法一：哈希表统计

核心思想：统计每个数字出现的次数。

方法二：摩尔投票法

核心思想：利用多数元素出现次数超过一半的特性。

• 维护护候选元素和计数
• 如果当前元素等于候选元素，计数+1
• 否则计数-1，如果计数为0，更换候选元素

时间复杂度：O(n) 空间复杂度：O(n)（方法一）或 O(1)（方法二）

Python 实现

# 方法一：哈希表
def majority_element_hash(nums):
    """
    使用哈希表统计
    """
    from collections import Counter
    count = Counter(nums)
    n = len(nums)
    for num, freq in count.items():
        if freq > n // 2:
            return num
    return -1


# 方法二：摩尔投票法
def majority_element(nums):
    """
    使用摩尔投票法
    """
    if not nums:
        return -1

    candidate = None
    count = 0

    for num in nums:
        if count == 0:
            candidate = num
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1

    return candidate


# 测试代码
if __name__ == "__main__":
    test_cases = [
        [1, 2, 3, 2, 2, 2, 5, 4, 2],
        [1, 1, 1, 2, 3],
        [3, 3, 4, 2, 4, 4, 4, 4, 4],
    ]

    for nums in test_cases:
        print(f"{nums} → {majority_element(nums)}")

# 输出:
# [1, 2, 3, 2, 2, 2, 5, 4, 2] → 2
# [1, 1, 1, 2, 3] → 1
# [3, 3, 4, 2, 4, 4, 4, 4, 4] → 4

图解

摩尔投票法示例: [1, 2, 3, 2, 2, 2, 5, 4, 2]

candidate=None, count=0

1: count=0, candidate=1, count=1
2: 2≠1, count=0
3: count=0, candidate=3, count=1
2: 2≠3, count=0
2: count=0, candidate=2, count=1
2: 2=2, count=2
5: 5≠2, count=1
4: 4≠2, count=0
2: count=0, candidate=2, count=1

最终candidate=2

原理: 多数元素出现的次数超过其他元素的总和
所以最后剩下的必然是多数元素