題目描述:設計一個 SummaryRanges 類別,支援兩個操作:addNum(val) 將整數 val 加入資料流;getIntervals() 回傳所有不相交的閉合區間(升序排列),涵蓋目前資料流中所有數字。
解題思路:使用 std::map<int,int> intervals,以區間起點(start)為 key,終點(end)為 value,維護所有不相交區間集合。
addNum(val) 執行步驟:
val 是否已在某個現有區間內,若是則直接返回(避免重複處理)。auto right = intervals.lower_bound(val)——第一個 start ≥ val 的區間。right != begin(),則 left = prev(right)——start < val 的最近區間。left->second >= val - 1,表示左鄰的 end ≥ val-1,新數字緊貼或重疊左鄰。right->first <= val + 1,表示右鄰的 start ≤ val+1,新數字緊貼或重疊右鄰。時間複雜度:addNum — O(log n),其中 n 為目前不相交區間數量(map 的 lower_bound 和 erase 均為 O(log n));getIntervals — O(k),k 為區間數量。
空間複雜度:O(n) — map 儲存最多 n 個不相交區間(n 為加入的不同數字個數)。
addNum(val):
right = first interval with start >= val
if left neighbor exists and left.end >= val: return (already covered)
mergeLeft = left neighbor exists AND left.end >= val - 1
mergeRight = right exists AND right.start <= val + 1
if mergeLeft AND mergeRight:
left.end = max(left.end, right.end)
erase right
else if mergeLeft:
left.end = max(left.end, val)
else if mergeRight:
newEnd = right.end; erase right; insert [val, newEnd]
else:
insert [val, val]
getIntervals():
for each (start, end) in map:
append [start, end] to result
return result有序集合 + 二分搜尋(TreeSet):在 Java 中可用 TreeSet 配合 floor/ceiling 操作,原理相同,但 C++ 的 std::map 已是此模式的最佳實踐。
排序陣列 + 每次 getIntervals 合併:每次 addNum 只將值塞入一個 unordered_set,每次 getIntervals 時取出所有值排序並線性合併。優點是 addNum 為 O(1),缺點是 getIntervals 為 O(n log n),適合寫多讀少的場景。
線段樹 / 二元索引樹(BIT):在值域範圍固定(如 0~10⁴)時,可用線段樹維護覆蓋區間,addNum 和 getIntervals 均為 O(log V),適合值域小但呼叫頻繁的場景。
removeNum(val) 操作,std::map 的設計應如何修改?getIntervals 呼叫頻率遠低於 addNum,選擇哪種實作方式更好?請分析時間與空間的取捨。