MediumRating 1423

3737. Count Subarrays With Majority Element I

arrayhash-tabledivide-and-conquersegment-treemerge-sortcountingprefix-sum

解題說明

Count Subarrays With Majority Element I

題目描述：給定一個整數陣列 nums 和一個整數 k，計算有多少個子陣列中 k 是多數元素（即 k 的出現次數嚴格超過子陣列長度的一半）。

解題思路：利用前綴和轉化。定義轉換陣列：若 nums[i] == k 則為 +1，否則為 -1。則 k 在子陣列 [i, j] 中是多數元素等價於前綴和 prefix[j+1] - prefix[i] > 0。問題轉化為：計算有多少對 (i, j) 滿足 i < j 且 prefix[j] > prefix[i]。

這就是經典的「逆序對計數」的反面 — 計算正序對的數量。可以用歸併排序或樹狀陣列（BIT）在 O(n log n) 時間內解決。但由於資料範圍可能不大，也可以用前綴和 + 雜湊表直接計數。

C++ 解法

複雜度分析

時間複雜度：O(n log n) — 遍歷陣列一次，每個元素做一次 BIT 更新和查詢，各 O(log n)。

空間複雜度：O(n) — 樹狀陣列大小為 O(n)。

虛擬碼

1. Transform nums: +1 if element == k, -1 otherwise
2. Compute prefix sums: prefix[0] = 0, prefix[i+1] = prefix[i] + transformed[i]
3. Count pairs (i, j) where i < j and prefix[j] > prefix[i]
4. Use Fenwick tree (BIT):
   a. Insert prefix[0] = 0
   b. For each new prefix value p, query count of values < p, add to result
   c. Insert p into BIT
5. Return total count

其他解法

歸併排序 O(n log n)：在歸併排序過程中計算正序對數量。每次合併左右兩半時，計算左邊 prefix < 右邊 prefix 的對數。與逆序對計數的經典方法類似。

暴力法 O(n²)：枚舉所有子陣列，逐一統計 k 的出現次數，判斷是否為多數。簡單但 n 較大時超時。

延伸思考

如果要求 k 的出現次數至少為子陣列長度的 1/3（而非超過 1/2），如何修改轉換方式？
若有多個候選的多數元素（不只一個 k），如何統計包含任一多數元素的子陣列？
能否用 Boyer-Moore 投票算法的思想來解決此問題？

Count Subarrays With Majority Element I — CaffeCode