HardRating 2205

1157. Online Majority Element In Subarray

arraybinary-searchdesignbinary-indexed-treesegment-tree

解題說明

Online Majority Element In Subarray

題目描述：設計一個資料結構，支援查詢：給定子陣列 [left, right] 和閾值 threshold，判斷是否存在一個元素在該子陣列中出現次數 >= threshold。如果存在，返回該元素；否則返回 -1。保證如果存在答案，該元素出現次數 > (right - left + 1) / 2。

解題思路：

隨機化 + 二分搜尋：由於答案（如果存在）是多數元素（出現次數 > 一半），隨機選一個子陣列中的元素，有超過 50% 的概率是答案。
預處理：對每個值建立其出現位置的有序列表。
查詢時：隨機選子陣列中的一個元素，用二分搜尋計算它在 [left, right] 中的出現次數。重複 20-30 次，如果都找不到滿足閾值的元素，返回 -1。
錯誤概率：每次不命中概率 < 1/2，重複 30 次後錯誤概率 < 2^(-30) ≈ 10^(-9)。

C++ 解法

複雜度分析

時間複雜度：建構 O(n)；每次查詢 O(30 * log n)，其中 log n 為二分搜尋

空間複雜度：O(n) — 存儲每個值的位置列表

虛擬碼

1. Preprocessing:
   a. For each value, store sorted list of its positions
2. Query(left, right, threshold):
   a. Repeat 30 times:
      - Randomly pick an index in [left, right]
      - Get the candidate value at that index
      - Binary search to count occurrences in [left, right]
      - If count >= threshold: return candidate
   b. Return -1 (no majority element found)

其他解法

線段樹 + Boyer-Moore Voting：線段樹的每個節點存儲該區間的候選多數元素。查詢時合併區間候選，再用二分搜尋驗證出現次數。建構 O(n)，查詢 O(log^2 n)。空間 O(n)。確定性算法，無隨機性。
分塊算法（Sqrt Decomposition）：將陣列分成 sqrt(n) 大小的塊。預處理每個塊的頻率。查詢時合併涉及的塊來找候選答案。時間複雜度 O(sqrt(n)) per query。

延伸思考

如果 threshold 不一定 > (right-left+1)/2（不保證是多數元素），隨機化方法還能用嗎？
如何設計一個完全確定性的解法？
如果陣列會動態修改（插入/刪除元素），如何維護這個資料結構？

Online Majority Element In Subarray — CaffeCode