LeetCode如何求众数

# LeetCode如何求众数

## 什么是众数

众数（Mode）是统计学中的概念，指在一组数据中出现次数最多的数值。与平均数、中位数不同，众数反映的是数据的集中趋势中最常见的值。例如：
- 数据集 `[1, 2, 2, 3]` 的众数是 `2`
- 数据集 `[1, 1, 2, 2]` 的众数是 `1` 和 `2`（多众数情况）

在LeetCode中，典型的众数问题如 **169. Majority Element**（多数元素），要求找出出现次数超过 `⌊n/2⌋` 次的元素。

---

## 常见解法与代码实现

### 方法一：哈希表统计法

**核心思想**：通过哈希表记录每个元素的出现次数，最后返回出现次数最多的元素。

```python
def majorityElement(nums):
    counts = {}
    for num in nums:
        counts[num] = counts.get(num, 0) + 1
    return max(counts.keys(), key=counts.get)

复杂度分析： - 时间复杂度：O(n)，遍历数组一次 - 空间复杂度：O(n)，最坏情况下需要存储所有元素

方法二：排序法

核心思想：排序后，众数一定会出现在数组中间位置（仅适用于多数元素问题）。

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

复杂度分析： - 时间复杂度：O(n log n)，取决于排序算法 - 空间复杂度：O(1) 或 O(n)，视排序实现而定

方法三：摩尔投票法（Boyer-Moore Algorithm）

最优解：适用于出现次数超过一半的众数问题。通过抵消不同元素的方式找到候选众数。

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

复杂度分析： - 时间复杂度：O(n)，单次遍历 - 空间复杂度：O(1)

变式问题与解决方案

问题1：存在多个众数（如LeetCode 229. Majority Element II）

要求：找出所有出现次数超过 ⌊n/3⌋ 次的元素。

解法：扩展摩尔投票法，维护两个候选数。

def majorityElement(nums):
    candidate1, candidate2 = None, None
    count1, count2 = 0, 0
    for num in nums:
        if num == candidate1:
            count1 += 1
        elif num == candidate2:
            count2 += 1
        elif count1 == 0:
            candidate1 = num
            count1 = 1
        elif count2 == 0:
            candidate2 = num
            count2 = 1
        else:
            count1 -= 1
            count2 -= 1
    # 二次验证
    result = []
    for candidate in [candidate1, candidate2]:
        if nums.count(candidate) > len(nums) // 3:
            result.append(candidate)
    return result

问题2：流式数据中的众数

当数据以流的形式输入且无法存储全部数据时，可使用空间优化的哈希表或抽样统计法。

边界条件与注意事项

1. 空数组处理：需明确返回规则（如返回None或抛出异常）
2. 无众数情况：例如 [1,2,3] 需要特殊处理
3. 浮点数众数：需考虑精度问题（如 1.0 和 1 是否算相同）
4. 多众数输出顺序：题目可能要求按升序返回

实际应用场景

1. 数据分析：统计用户行为中的高频事件
2. 系统监控：检测异常高频出现的错误日志
3. 推荐系统：找出用户最常点击的商品类别

扩展思考

• 如果内存有限，如何用O(1)空间复杂度解决问题？（参考摩尔投票法）
• 如何并行化处理超大规模数据的众数统计？（Map-Reduce思路）
• 在数据库SQL中如何高效计算众数？（GROUP BY + COUNT 组合）

总结

推荐选择： - 面试优先选择摩尔投票法（考察算法思维） - 工程实践可考虑哈希表（代码可读性高） “`

（注：全文约1200字，可根据需要增减代码示例或详细说明部分）