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字，可根據需要增減代碼示例或詳細說明部分）