LeetCode如何求数组中出现次数超过一半的数字

# LeetCode如何求数组中出现次数超过一半的数字

## 问题描述
在LeetCode的面试题中，常会遇到这样一个问题：给定一个大小为n的数组，找出其中出现次数超过⌊n/2⌋次的数字。例如：
- 输入：[3,2,3]  
  输出：3  
- 输入：[2,2,1,1,1,2,2]  
  输出：2

## 常见解法分析

### 方法一：哈希表统计法
**时间复杂度：O(n)**  
**空间复杂度：O(n)**  
通过哈希表记录每个数字出现的次数，最后遍历哈希表找到满足条件的数字。

```python
def majorityElement(nums):
    counts = {}
    for num in nums:
        counts[num] = counts.get(num, 0) + 1
        if counts[num] > len(nums) // 2:
            return num

优点：思路直观，适用于任何数据分布
缺点：需要额外空间存储哈希表

方法二：排序法

时间复杂度：O(nlogn)
空间复杂度：O(1)或O(n)（取决于是否原地排序）
将数组排序后，中间位置的元素必定是众数。

def majorityElement(nums):
    nums.sort()
    return nums[len(nums)//2]

优点：代码简洁
缺点：修改了原数组，排序耗时较高

方法三：摩尔投票法（最优解）

时间复杂度：O(n)
空间复杂度：O(1)
通过抵消策略找到可能的主元素，最终验证其是否满足条件。

def majorityElement(nums):
    candidate, count = None, 0
    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)
    return candidate

核心思想： 1. 初始化候选人和计数器 2. 遍历时遇到相同数字则+1，不同则-1 3. 计数器归零时更换候选人

优势：不需要额外空间，线性时间完成

边界情况处理

• 空数组输入：应返回异常或None
• 不存在满足条件的数字：题目保证存在解（根据题意）
• 极长数组（10^5级别）：优先选择摩尔投票法

实际应用场景

这种算法在以下场景中有重要应用： 1. 大规模数据统计（如选举计票） 2. 实时系统中的多数元素检测 3. 数据压缩中的高频值处理

总结

在面试中，建议优先解释摩尔投票法的思路，其高效的时空复杂度往往能体现算法优化能力。 “`