據(jù)流變?yōu)槎鄠€(gè)不相交區(qū)間：LeetCode 0352 的設(shè)計(jì)題解析與「集合 + 動(dòng)態(tài)生成」實(shí)戰(zhàn)方案)
教程文檔知識(shí)庫(kù)【免費(fèi)下載鏈接】AlgoNote??「算法通關(guān)手冊(cè)」從零開(kāi)始的「算法與數(shù)據(jù)結(jié)構(gòu)」學(xué)習(xí)教程200 道「算法面試熱門題目」1000 道「LeetCode 題目解析」持續(xù)更新中項(xiàng)目地址https://gitcode.com/gh_mirrors/le/AlgoNote點(diǎn)擊查看免費(fèi)下載本篇技術(shù)指南基于 AlgoNote 算法通關(guān)手冊(cè)中 0352. 將數(shù)據(jù)流變?yōu)槎鄠€(gè)不相交區(qū)間 的題解深入講解如何設(shè)計(jì)一個(gè)SummaryRanges類把動(dòng)態(tài)輸入的非負(fù)整數(shù)數(shù)據(jù)流實(shí)時(shí)總結(jié)為不相交區(qū)間列表。讀完本篇你將掌握「哈希集合去重 排序后線性掃描合并區(qū)間」的經(jīng)典設(shè)計(jì)思路、對(duì)應(yīng)的完整可運(yùn)行 Python 實(shí)現(xiàn)并能理解其在大量合并、區(qū)間數(shù)量稀少場(chǎng)景下的優(yōu)化方向。一、題目回顧數(shù)據(jù)流與不相交區(qū)間描述給定一個(gè)由非負(fù)整數(shù) $a1, a2, ..., an$ 組成的數(shù)據(jù)流輸入需要將到目前為止看到的數(shù)字總結(jié)為不相交的區(qū)間列表。要求實(shí)現(xiàn)SummaryRanges類SummaryRanges()使用一個(gè)空數(shù)據(jù)流初始化對(duì)象。void addNum(int val)向數(shù)據(jù)流中加入整數(shù) $val$。int[][] getIntervals()以不相交區(qū)間 $[start_i, end_i]$ 的列表形式返回對(duì)數(shù)據(jù)流中整數(shù)的總結(jié)。說(shuō)明$0 \le val \le 10^{4}$。最多調(diào)用addNum和getIntervals方法 $3 \times 10^{4}$ 次。進(jìn)階如果存在大量合并并且與數(shù)據(jù)流的大小相比不相交區(qū)間的數(shù)量很小該怎么辦示例輸入 [SummaryRanges, addNum, getIntervals, addNum, getIntervals, addNum, getIntervals, addNum, getIntervals, addNum, getIntervals] [[], [1], [], [3], [], [7], [], [2], [], [6], []] 輸出 [null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]] 解釋 SummaryRanges summaryRanges new SummaryRanges(); summaryRanges.addNum(1); // arr [1] summaryRanges.getIntervals(); // 返回 [[1, 1]] summaryRanges.addNum(3); // arr [1, 3] summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3]] summaryRanges.addNum(7); // arr [1, 3, 7] summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3], [7, 7]] summaryRanges.addNum(2); // arr [1, 2, 3, 7] summaryRanges.getIntervals(); // 返回 [[1, 3], [7, 7]] summaryRanges.addNum(6); // arr [1, 2, 3, 6, 7] summaryRanges.getIntervals(); // 返回 [[1, 3], [6, 7]]從示例可以直觀看出關(guān)鍵規(guī)律數(shù)字1、2、3連續(xù)合并為[1, 3]數(shù)字6、7連續(xù)合并為[6, 7]。所謂「不相交區(qū)間」本質(zhì)就是值域上連續(xù)的一段整數(shù)這正是本倉(cāng)庫(kù)中「區(qū)間類問(wèn)題」一貫的處理對(duì)象。二、解題思路集合 動(dòng)態(tài)生成區(qū)間這道題的核心是維護(hù)一個(gè)數(shù)字集合然后在需要時(shí)動(dòng)態(tài)生成不相交的區(qū)間列表。其標(biāo)簽為「設(shè)計(jì)、二分查找、有序集合」在本題解中我們先從最簡(jiǎn)單、最易于驗(yàn)證正確性的「集合 動(dòng)態(tài)生成」方案講起。2.1 算法思路數(shù)據(jù)結(jié)構(gòu)選擇使用集合set存儲(chǔ)所有出現(xiàn)過(guò)的數(shù)字利用集合的去重特性自動(dòng)處理重復(fù)數(shù)字——同一個(gè)數(shù)字多次addNum只保留一份不會(huì)影響區(qū)間劃分。添加數(shù)字當(dāng)添加數(shù)字 $val$ 時(shí)直接將其加入集合中時(shí)間復(fù)雜度為 $O(1)$。獲取區(qū)間當(dāng)需要獲取區(qū)間列表時(shí)將集合中的所有數(shù)字排序。遍歷排序后的數(shù)字連續(xù)的數(shù)字合并為一個(gè)區(qū)間。遇到不連續(xù)的數(shù)字時(shí)開(kāi)始新的區(qū)間。2.2 具體步驟使用集合存儲(chǔ)所有添加的數(shù)字。addNum(val)將 $val$ 添加到集合中。getIntervals()對(duì)集合中的數(shù)字排序得到 $sorted_nums$。初始化 $start end sorted_nums[0]$。遍歷剩余數(shù)字如果 $sorted_nums[i] end 1$則擴(kuò)展當(dāng)前區(qū)間 $end sorted_nums[i]$。否則保存當(dāng)前區(qū)間 $[start, end]$開(kāi)始新區(qū)間 $start end sorted_nums[i]$。最后添加最后一個(gè)區(qū)間。這一「排序 → 掃描 → 按連續(xù)性切分」的流程與倉(cāng)庫(kù)中 0228. 匯總區(qū)間 的「雙指針」思路同源后者對(duì)靜態(tài)有序數(shù)組用nums[j 1] nums[j] 1判斷連續(xù)性前者對(duì)動(dòng)態(tài)無(wú)序集合先排序再判斷sorted_nums[i] end 1兩者共用同一個(gè)核心不變量——后一個(gè)數(shù)恰好比前一個(gè)數(shù)大 1 時(shí)合并。2.3 代碼class SummaryRanges: def __init__(self): # 使用集合存儲(chǔ)所有出現(xiàn)過(guò)的數(shù)字 self.nums set() def addNum(self, value: int) - None: # 將數(shù)字添加到集合中集合自動(dòng)去重 self.nums.add(value) def getIntervals(self) - List[List[int]]: # 如果集合為空返回空列表 if not self.nums: return [] # 將集合中的數(shù)字排序 sorted_nums sorted(self.nums) intervals [] # 初始化第一個(gè)區(qū)間 start end sorted_nums[0] # 遍歷剩余數(shù)字構(gòu)建區(qū)間 for i in range(1, len(sorted_nums)): if sorted_nums[i] end 1: # 當(dāng)前數(shù)字與前一個(gè)數(shù)字連續(xù)擴(kuò)展當(dāng)前區(qū)間 end sorted_nums[i] else: # 當(dāng)前數(shù)字與前一個(gè)數(shù)字不連續(xù)保存當(dāng)前區(qū)間并開(kāi)始新區(qū)間 intervals.append([start, end]) start end sorted_nums[i] # 添加最后一個(gè)區(qū)間 intervals.append([start, end]) return intervals # Your SummaryRanges object will be instantiated and called as such: # obj SummaryRanges() # obj.addNum(value) # param_2 obj.getIntervals()2.4 復(fù)雜度分析時(shí)間復(fù)雜度addNum(val)$O(1)$集合的插入操作時(shí)間復(fù)雜度為常數(shù)。getIntervals()$O(n \log n)$其中 $n$ 為集合中數(shù)字的個(gè)數(shù)主要時(shí)間消耗在排序上。空間復(fù)雜度$O(n)$其中 $n$ 為添加的不同數(shù)字的個(gè)數(shù)。三、進(jìn)階場(chǎng)景剖析大量合并、區(qū)間稀少時(shí)怎么辦原題給出了一條進(jìn)階問(wèn)題如果存在大量合并并且與數(shù)據(jù)流的大小相比不相交區(qū)間的數(shù)量很小該怎么辦先分析上面「集合 動(dòng)態(tài)生成」方案在進(jìn)階場(chǎng)景下的瓶頸getIntervals()每次都要對(duì)整個(gè)集合排序復(fù)雜度為 $O(n \log n)$。即便最終只有少數(shù)幾個(gè)區(qū)間只要數(shù)據(jù)量大最多 $3 \times 10^4$ 次調(diào)用、$val$ 取值范圍 $0 \le val \le 10^4$排序成本依然可觀。可以推斷更貼合進(jìn)階要求的做法是讓區(qū)間在addNum時(shí)增量維護(hù)而不是在getIntervals時(shí)全量重建用有序集合如 C 的std::set、Python 中借助sortedcontainers或二分查找維護(hù)的列表保存當(dāng)前的區(qū)間起點(diǎn)。addNum(val)時(shí)通過(guò)二分查找定位val的前驅(qū)與后繼區(qū)間判斷是否滿足合并條件val落在某個(gè)已有區(qū)間[start, end]內(nèi)部start val end無(wú)需任何操作val end 1緊鄰左區(qū)間右側(cè)擴(kuò)展左區(qū)間的右端點(diǎn)val next_start - 1緊鄰右區(qū)間左側(cè)擴(kuò)展右區(qū)間的左端點(diǎn)兩者同時(shí)成立將左、右兩個(gè)區(qū)間與val三者合并為一個(gè)新區(qū)間都不成立val作為孤立點(diǎn)形成新的單點(diǎn)區(qū)間[val, val]。getIntervals()直接返回有序集合中已維護(hù)的區(qū)間列表復(fù)雜度為 $O(k)$其中 $k$ 為區(qū)間個(gè)數(shù)。在這種設(shè)計(jì)下單次addNum的復(fù)雜度約為 $O(\log k)$二分定位前驅(qū)后繼 $O(1)$合并而getIntervals的復(fù)雜度與區(qū)間數(shù)量 $k$ 成正比。當(dāng)區(qū)間數(shù)量 $k$ 遠(yuǎn)小于數(shù)據(jù)規(guī)模 $n$ 時(shí)整體表現(xiàn)遠(yuǎn)優(yōu)于「每次全量排序」。這也是本題標(biāo)簽中「二分查找、有序集合」的落點(diǎn)所在。四、同類區(qū)間題對(duì)照AlgoNote 中的區(qū)間問(wèn)題家族AlgoNote 的題解體系中區(qū)間相關(guān)的題目形成了一條清晰的進(jìn)階路線可幫助你橫向鞏固題目數(shù)據(jù)形態(tài)核心操作參考題解0228. 匯總區(qū)間靜態(tài)有序數(shù)組雙指針掃描nums[j1] nums[j] 1判連續(xù)簡(jiǎn)單難度雙指針 $O(n)$0056. 合并區(qū)間靜態(tài)無(wú)序區(qū)間列表按左端點(diǎn)排序后線性合并重疊區(qū)間經(jīng)典區(qū)間合并模板0352. 將數(shù)據(jù)流變?yōu)槎鄠€(gè)不相交區(qū)間動(dòng)態(tài)數(shù)據(jù)流集合去重 排序掃描或有序集合增量合并本題困難難度0729. 我的日程安排表 I動(dòng)態(tài)預(yù)約請(qǐng)求動(dòng)態(tài)開(kāi)點(diǎn)線段樹(shù)/有序集合判重設(shè)計(jì)類二分查找 有序集合其中與本題設(shè)計(jì)思路最接近的是 0729. 我的日程安排表 I同樣是「設(shè)計(jì)」標(biāo)簽下的動(dòng)態(tài)區(qū)間維護(hù)題同樣需要在每次插入時(shí)快速定位相鄰區(qū)間。區(qū)別在于 0729 關(guān)注的是區(qū)間是否沖突查詢 判重而 0352 關(guān)注的是區(qū)間如何合并插入 歸并兩者可以互為對(duì)照練習(xí)。五、小結(jié)回到本題核心要點(diǎn)可以概括為三句話正確性優(yōu)先addNum用集合 $O(1)$ 去重getIntervals排序后按end 1連續(xù)性切分區(qū)間思路直白、易于驗(yàn)證適合作為首版實(shí)現(xiàn)。性能進(jìn)階當(dāng)區(qū)間數(shù)量遠(yuǎn)小于數(shù)據(jù)量時(shí)把「全量重建」改為「增量合并」——用有序集合配合二分查找維護(hù)區(qū)間可把單次操作成本壓到 $O(\log k)$。橫向遷移區(qū)間判定與合并的思維可以復(fù)用到匯總區(qū)間、合并區(qū)間、日程安排等一整套區(qū)間題AlgoNote 的 0300-0399 題解目錄 與 LeetCode 題解列表 中收錄了大量同類題目供繼續(xù)練習(xí)。掌握「數(shù)據(jù)結(jié)構(gòu)選型決定復(fù)雜度」這一設(shè)計(jì)題的核心命題你就理解了本題乃至整個(gè)「設(shè)計(jì) 區(qū)間」類題目的通用解法框架。贊分享教程文檔知識(shí)庫(kù)【免費(fèi)下載鏈接】AlgoNote??「算法通關(guān)手冊(cè)」從零開(kāi)始的「算法與數(shù)據(jù)結(jié)構(gòu)」學(xué)習(xí)教程200 道「算法面試熱門題目」1000 道「LeetCode 題目解析」持續(xù)更新中項(xiàng)目地址https://gitcode.com/gh_mirrors/le/AlgoNote點(diǎn)擊查看免費(fèi)下載相關(guān)推薦Apache Beam Java 實(shí)戰(zhàn)用 FlattenWith 將多個(gè) PCollection 合并為單一數(shù)據(jù)流Apache Beam Java 實(shí)戰(zhàn)用 FlattenWith 將多個(gè) PCollection 合并為單一數(shù)據(jù)流 本文圍繞 Apache Beam 官方 J大數(shù)據(jù)批處理流處理數(shù)據(jù)工程如何在區(qū)塊鏈應(yīng)用中實(shí)現(xiàn)不可變數(shù)據(jù)存儲(chǔ)Objection.js ORM 終極集成指南 如何在區(qū)塊鏈應(yīng)用中實(shí)現(xiàn)不可變數(shù)據(jù)存儲(chǔ)Objection.js ORM 終極集成指南 Objection.js 是一個(gè)強(qiáng)大的 Node.js ORM對(duì)象數(shù)據(jù)庫(kù)后端leetcode 題解Number Stream to Intervals數(shù)據(jù)流區(qū)間合并雙哈希表與有序字典實(shí)現(xiàn)剖析leetcode 題解Number Stream to Intervals數(shù)據(jù)流區(qū)間合并雙哈希表與有序字典實(shí)現(xiàn)剖析 本篇技術(shù)指南以《leetcode 題解文檔教程知識(shí)庫(kù)上一篇Elden Ring存檔遷移終極指南3步安全轉(zhuǎn)移數(shù)百小時(shí)游戲進(jìn)度下一篇免費(fèi)開(kāi)源音頻頻譜分析神器Spek完整使用指南與深度解析創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考 將數(shù)據(jù)流變?yōu)槎鄠€(gè)不相交區(qū)間：LeetCode 0352 的設(shè)計(jì)題解析與「集合 + 動(dòng)態(tài)生成」實(shí)戰(zhàn)方案
教程文檔知識(shí)庫(kù)【免費(fèi)下載鏈接】AlgoNote??「算法通關(guān)手冊(cè)」從零開(kāi)始的「算法與數(shù)據(jù)結(jié)構(gòu)」學(xué)習(xí)教程200 道「算法面試熱門題目」1000 道「LeetCode 題目解析」持續(xù)更新中項(xiàng)目地址https://gitcode.com/gh_mirrors/le/AlgoNote點(diǎn)擊查看免費(fèi)下載本篇技術(shù)指南基于 AlgoNote 算法通關(guān)手冊(cè)中 0352. 將數(shù)據(jù)流變?yōu)槎鄠€(gè)不相交區(qū)間 的題解深入講解如何設(shè)計(jì)一個(gè)SummaryRanges類把動(dòng)態(tài)輸入的非負(fù)整數(shù)數(shù)據(jù)流實(shí)時(shí)總結(jié)為不相交區(qū)間列表。讀完本篇你將掌握「哈希集合去重 排序后線性掃描合并區(qū)間」的經(jīng)典設(shè)計(jì)思路、對(duì)應(yīng)的完整可運(yùn)行 Python 實(shí)現(xiàn)并能理解其在大量合并、區(qū)間數(shù)量稀少場(chǎng)景下的優(yōu)化方向。一、題目回顧數(shù)據(jù)流與不相交區(qū)間描述給定一個(gè)由非負(fù)整數(shù) $a1, a2, ..., an$ 組成的數(shù)據(jù)流輸入需要將到目前為止看到的數(shù)字總結(jié)為不相交的區(qū)間列表。要求實(shí)現(xiàn)SummaryRanges類SummaryRanges()使用一個(gè)空數(shù)據(jù)流初始化對(duì)象。void addNum(int val)向數(shù)據(jù)流中加入整數(shù) $val$。int[][] getIntervals()以不相交區(qū)間 $[start_i, end_i]$ 的列表形式返回對(duì)數(shù)據(jù)流中整數(shù)的總結(jié)。說(shuō)明$0 \le val \le 10^{4}$。最多調(diào)用addNum和getIntervals方法 $3 \times 10^{4}$ 次。進(jìn)階如果存在大量合并并且與數(shù)據(jù)流的大小相比不相交區(qū)間的數(shù)量很小該怎么辦示例輸入 [SummaryRanges, addNum, getIntervals, addNum, getIntervals, addNum, getIntervals, addNum, getIntervals, addNum, getIntervals] [[], [1], [], [3], [], [7], [], [2], [], [6], []] 輸出 [null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]] 解釋 SummaryRanges summaryRanges new SummaryRanges(); summaryRanges.addNum(1); // arr [1] summaryRanges.getIntervals(); // 返回 [[1, 1]] summaryRanges.addNum(3); // arr [1, 3] summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3]] summaryRanges.addNum(7); // arr [1, 3, 7] summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3], [7, 7]] summaryRanges.addNum(2); // arr [1, 2, 3, 7] summaryRanges.getIntervals(); // 返回 [[1, 3], [7, 7]] summaryRanges.addNum(6); // arr [1, 2, 3, 6, 7] summaryRanges.getIntervals(); // 返回 [[1, 3], [6, 7]]從示例可以直觀看出關(guān)鍵規(guī)律數(shù)字1、2、3連續(xù)合并為[1, 3]數(shù)字6、7連續(xù)合并為[6, 7]。所謂「不相交區(qū)間」本質(zhì)就是值域上連續(xù)的一段整數(shù)這正是本倉(cāng)庫(kù)中「區(qū)間類問(wèn)題」一貫的處理對(duì)象。二、解題思路集合 動(dòng)態(tài)生成區(qū)間這道題的核心是維護(hù)一個(gè)數(shù)字集合然后在需要時(shí)動(dòng)態(tài)生成不相交的區(qū)間列表。其標(biāo)簽為「設(shè)計(jì)、二分查找、有序集合」在本題解中我們先從最簡(jiǎn)單、最易于驗(yàn)證正確性的「集合 動(dòng)態(tài)生成」方案講起。2.1 算法思路數(shù)據(jù)結(jié)構(gòu)選擇使用集合set存儲(chǔ)所有出現(xiàn)過(guò)的數(shù)字利用集合的去重特性自動(dòng)處理重復(fù)數(shù)字——同一個(gè)數(shù)字多次addNum只保留一份不會(huì)影響區(qū)間劃分。添加數(shù)字當(dāng)添加數(shù)字 $val$ 時(shí)直接將其加入集合中時(shí)間復(fù)雜度為 $O(1)$。獲取區(qū)間當(dāng)需要獲取區(qū)間列表時(shí)將集合中的所有數(shù)字排序。遍歷排序后的數(shù)字連續(xù)的數(shù)字合并為一個(gè)區(qū)間。遇到不連續(xù)的數(shù)字時(shí)開(kāi)始新的區(qū)間。2.2 具體步驟使用集合存儲(chǔ)所有添加的數(shù)字。addNum(val)將 $val$ 添加到集合中。getIntervals()對(duì)集合中的數(shù)字排序得到 $sorted_nums$。初始化 $start end sorted_nums[0]$。遍歷剩余數(shù)字如果 $sorted_nums[i] end 1$則擴(kuò)展當(dāng)前區(qū)間 $end sorted_nums[i]$。否則保存當(dāng)前區(qū)間 $[start, end]$開(kāi)始新區(qū)間 $start end sorted_nums[i]$。最后添加最后一個(gè)區(qū)間。這一「排序 → 掃描 → 按連續(xù)性切分」的流程與倉(cāng)庫(kù)中 0228. 匯總區(qū)間 的「雙指針」思路同源后者對(duì)靜態(tài)有序數(shù)組用nums[j 1] nums[j] 1判斷連續(xù)性前者對(duì)動(dòng)態(tài)無(wú)序集合先排序再判斷sorted_nums[i] end 1兩者共用同一個(gè)核心不變量——后一個(gè)數(shù)恰好比前一個(gè)數(shù)大 1 時(shí)合并。2.3 代碼class SummaryRanges: def __init__(self): # 使用集合存儲(chǔ)所有出現(xiàn)過(guò)的數(shù)字 self.nums set() def addNum(self, value: int) - None: # 將數(shù)字添加到集合中集合自動(dòng)去重 self.nums.add(value) def getIntervals(self) - List[List[int]]: # 如果集合為空返回空列表 if not self.nums: return [] # 將集合中的數(shù)字排序 sorted_nums sorted(self.nums) intervals [] # 初始化第一個(gè)區(qū)間 start end sorted_nums[0] # 遍歷剩余數(shù)字構(gòu)建區(qū)間 for i in range(1, len(sorted_nums)): if sorted_nums[i] end 1: # 當(dāng)前數(shù)字與前一個(gè)數(shù)字連續(xù)擴(kuò)展當(dāng)前區(qū)間 end sorted_nums[i] else: # 當(dāng)前數(shù)字與前一個(gè)數(shù)字不連續(xù)保存當(dāng)前區(qū)間并開(kāi)始新區(qū)間 intervals.append([start, end]) start end sorted_nums[i] # 添加最后一個(gè)區(qū)間 intervals.append([start, end]) return intervals # Your SummaryRanges object will be instantiated and called as such: # obj SummaryRanges() # obj.addNum(value) # param_2 obj.getIntervals()2.4 復(fù)雜度分析時(shí)間復(fù)雜度addNum(val)$O(1)$集合的插入操作時(shí)間復(fù)雜度為常數(shù)。getIntervals()$O(n \log n)$其中 $n$ 為集合中數(shù)字的個(gè)數(shù)主要時(shí)間消耗在排序上。空間復(fù)雜度$O(n)$其中 $n$ 為添加的不同數(shù)字的個(gè)數(shù)。三、進(jìn)階場(chǎng)景剖析大量合并、區(qū)間稀少時(shí)怎么辦原題給出了一條進(jìn)階問(wèn)題如果存在大量合并并且與數(shù)據(jù)流的大小相比不相交區(qū)間的數(shù)量很小該怎么辦先分析上面「集合 動(dòng)態(tài)生成」方案在進(jìn)階場(chǎng)景下的瓶頸getIntervals()每次都要對(duì)整個(gè)集合排序復(fù)雜度為 $O(n \log n)$。即便最終只有少數(shù)幾個(gè)區(qū)間只要數(shù)據(jù)量大最多 $3 \times 10^4$ 次調(diào)用、$val$ 取值范圍 $0 \le val \le 10^4$排序成本依然可觀。可以推斷更貼合進(jìn)階要求的做法是讓區(qū)間在addNum時(shí)增量維護(hù)而不是在getIntervals時(shí)全量重建用有序集合如 C 的std::set、Python 中借助sortedcontainers或二分查找維護(hù)的列表保存當(dāng)前的區(qū)間起點(diǎn)。addNum(val)時(shí)通過(guò)二分查找定位val的前驅(qū)與后繼區(qū)間判斷是否滿足合并條件val落在某個(gè)已有區(qū)間[start, end]內(nèi)部start val end無(wú)需任何操作val end 1緊鄰左區(qū)間右側(cè)擴(kuò)展左區(qū)間的右端點(diǎn)val next_start - 1緊鄰右區(qū)間左側(cè)擴(kuò)展右區(qū)間的左端點(diǎn)兩者同時(shí)成立將左、右兩個(gè)區(qū)間與val三者合并為一個(gè)新區(qū)間都不成立val作為孤立點(diǎn)形成新的單點(diǎn)區(qū)間[val, val]。getIntervals()直接返回有序集合中已維護(hù)的區(qū)間列表復(fù)雜度為 $O(k)$其中 $k$ 為區(qū)間個(gè)數(shù)。在這種設(shè)計(jì)下單次addNum的復(fù)雜度約為 $O(\log k)$二分定位前驅(qū)后繼 $O(1)$合并而getIntervals的復(fù)雜度與區(qū)間數(shù)量 $k$ 成正比。當(dāng)區(qū)間數(shù)量 $k$ 遠(yuǎn)小于數(shù)據(jù)規(guī)模 $n$ 時(shí)整體表現(xiàn)遠(yuǎn)優(yōu)于「每次全量排序」。這也是本題標(biāo)簽中「二分查找、有序集合」的落點(diǎn)所在。四、同類區(qū)間題對(duì)照AlgoNote 中的區(qū)間問(wèn)題家族AlgoNote 的題解體系中區(qū)間相關(guān)的題目形成了一條清晰的進(jìn)階路線可幫助你橫向鞏固題目數(shù)據(jù)形態(tài)核心操作參考題解0228. 匯總區(qū)間靜態(tài)有序數(shù)組雙指針掃描nums[j1] nums[j] 1判連續(xù)簡(jiǎn)單難度雙指針 $O(n)$0056. 合并區(qū)間靜態(tài)無(wú)序區(qū)間列表按左端點(diǎn)排序后線性合并重疊區(qū)間經(jīng)典區(qū)間合并模板0352. 將數(shù)據(jù)流變?yōu)槎鄠€(gè)不相交區(qū)間動(dòng)態(tài)數(shù)據(jù)流集合去重 排序掃描或有序集合增量合并本題困難難度0729. 我的日程安排表 I動(dòng)態(tài)預(yù)約請(qǐng)求動(dòng)態(tài)開(kāi)點(diǎn)線段樹(shù)/有序集合判重設(shè)計(jì)類二分查找 有序集合其中與本題設(shè)計(jì)思路最接近的是 0729. 我的日程安排表 I同樣是「設(shè)計(jì)」標(biāo)簽下的動(dòng)態(tài)區(qū)間維護(hù)題同樣需要在每次插入時(shí)快速定位相鄰區(qū)間。區(qū)別在于 0729 關(guān)注的是區(qū)間是否沖突查詢 判重而 0352 關(guān)注的是區(qū)間如何合并插入 歸并兩者可以互為對(duì)照練習(xí)。五、小結(jié)回到本題核心要點(diǎn)可以概括為三句話正確性優(yōu)先addNum用集合 $O(1)$ 去重getIntervals排序后按end 1連續(xù)性切分區(qū)間思路直白、易于驗(yàn)證適合作為首版實(shí)現(xiàn)。性能進(jìn)階當(dāng)區(qū)間數(shù)量遠(yuǎn)小于數(shù)據(jù)量時(shí)把「全量重建」改為「增量合并」——用有序集合配合二分查找維護(hù)區(qū)間可把單次操作成本壓到 $O(\log k)$。橫向遷移區(qū)間判定與合并的思維可以復(fù)用到匯總區(qū)間、合并區(qū)間、日程安排等一整套區(qū)間題AlgoNote 的 0300-0399 題解目錄 與 LeetCode 題解列表 中收錄了大量同類題目供繼續(xù)練習(xí)。掌握「數(shù)據(jù)結(jié)構(gòu)選型決定復(fù)雜度」這一設(shè)計(jì)題的核心命題你就理解了本題乃至整個(gè)「設(shè)計(jì) 區(qū)間」類題目的通用解法框架。贊分享教程文檔知識(shí)庫(kù)【免費(fèi)下載鏈接】AlgoNote??「算法通關(guān)手冊(cè)」從零開(kāi)始的「算法與數(shù)據(jù)結(jié)構(gòu)」學(xué)習(xí)教程200 道「算法面試熱門題目」1000 道「LeetCode 題目解析」持續(xù)更新中項(xiàng)目地址https://gitcode.com/gh_mirrors/le/AlgoNote點(diǎn)擊查看免費(fèi)下載相關(guān)推薦Apache Beam Java 實(shí)戰(zhàn)用 FlattenWith 將多個(gè) PCollection 合并為單一數(shù)據(jù)流Apache Beam Java 實(shí)戰(zhàn)用 FlattenWith 將多個(gè) PCollection 合并為單一數(shù)據(jù)流 本文圍繞 Apache Beam 官方 J大數(shù)據(jù)批處理流處理數(shù)據(jù)工程如何在區(qū)塊鏈應(yīng)用中實(shí)現(xiàn)不可變數(shù)據(jù)存儲(chǔ)Objection.js ORM 終極集成指南 如何在區(qū)塊鏈應(yīng)用中實(shí)現(xiàn)不可變數(shù)據(jù)存儲(chǔ)Objection.js ORM 終極集成指南 Objection.js 是一個(gè)強(qiáng)大的 Node.js ORM對(duì)象數(shù)據(jù)庫(kù)后端leetcode 題解Number Stream to Intervals數(shù)據(jù)流區(qū)間合并雙哈希表與有序字典實(shí)現(xiàn)剖析leetcode 題解Number Stream to Intervals數(shù)據(jù)流區(qū)間合并雙哈希表與有序字典實(shí)現(xiàn)剖析 本篇技術(shù)指南以《leetcode 題解文檔教程知識(shí)庫(kù)上一篇Elden Ring存檔遷移終極指南3步安全轉(zhuǎn)移數(shù)百小時(shí)游戲進(jìn)度下一篇免費(fèi)開(kāi)源音頻頻譜分析神器Spek完整使用指南與深度解析創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考