我去年處理過一個挺有意思的活兒某內(nèi)部工具需要在上億條日志里按時間窗口做聚合統(tǒng)計數(shù)據(jù)的時間戳全部落在最近三個月內(nèi)。一開始我按教科書思路上了紅黑樹、跳表這類“高級”結(jié)構(gòu)結(jié)果在真實數(shù)據(jù)上跑得還不如后來換上的一個普通數(shù)組快。原因很簡單——我知道時間戳的確定范圍明明可以用直接定址的思路偏要去搞那些對范圍無感的通用結(jié)構(gòu)。這件事給我的教訓(xùn)很直接算法選型先看數(shù)據(jù)范圍范圍一旦已知很多“復(fù)雜度更優(yōu)”的通用方案反而會被一個最樸素的數(shù)組下標(biāo)干掉。這篇內(nèi)容就想把“根據(jù)已知數(shù)據(jù)范圍選擇算法”這個話題掰開揉碎。我適合以下人群閱讀寫業(yè)務(wù)代碼時經(jīng)常面對確定值域的數(shù)據(jù)比如用戶ID、訂單號、IP段、時間戳、固定枚舉狀態(tài)卻不太確定該用哈希、樹還是數(shù)組的人刷題或做競賽時知道數(shù)據(jù)范圍卻總選錯算法的人以及工作中需要評估算法選型、做性能優(yōu)化的人?？赐昴憔兔靼追秶畔⒉皇强捎锌蔁o的細(xì)節(jié)而是能把算法復(fù)雜度從 O(n log n) 拉到 O(n) 甚至 O(1) 的關(guān)鍵鑰匙。1. “已知數(shù)據(jù)范圍”為什么能改變算法抉擇——從時間復(fù)雜度的盲區(qū)說起大多數(shù)人學(xué)算法時最先接觸的是時間復(fù)雜度的漸進(jìn)分析。這個工具很強(qiáng)大但它有一個致命盲區(qū)復(fù)雜度公式里往往只出現(xiàn) n元素個數(shù)而不出現(xiàn) U值域大小。結(jié)果就是當(dāng)問題里同時存在 n 和 U 這兩個維度時僅看 n 會嚴(yán)重誤導(dǎo)選型方向。1.1 一個反直覺的例子知道范圍后“笨算法”反而最快先看一個最經(jīng)典的場景給 10^7 個整數(shù)排序這 10^7 個數(shù)全部落在區(qū)間 [0, 10^5] 內(nèi)。常規(guī)思路是快速排序或歸并排序復(fù)雜度 O(n log n)。n 10^7 時10^7 × log2(10^7) ≈ 10^7 × 23.25大約 2.3 億次基本操作。跑起來一般需要幾百毫秒到一秒多具體看語言和優(yōu)化情況。但如果我知道所有數(shù)都落在 [0, 10^5] 這個有限范圍內(nèi)可以用計數(shù)排序// 已知arr[0..n-1] 中所有元素滿足 0 arr[i] U_MAX (U_MAX 100000) void countingSort(vectorint arr, int U_MAX) { vectorint cnt(U_MAX 1, 0); for (int x : arr) cnt[x]; int idx 0; for (int v 0; v U_MAX; v) { while (cnt[v]--) arr[idx] v; } }這段代碼的復(fù)雜度是 O(n U)其中 U 10^5。兩層循環(huán)加起來只有 10^7 10^5 的量級大約 1010 萬次操作比快速排序的 2.3 億次少了二十多倍。這里的關(guān)鍵不是“計數(shù)排序打敗快排”而是“在范圍已知的情況下復(fù)雜度分析必須同時考慮 n 和 U 兩個變量否則會得到錯誤結(jié)論”。如果你只會背“快排就是 O(n log n) 最優(yōu)”面對這種確定值域的數(shù)據(jù)就會錯過一個數(shù)量級的性能提升。1.2 數(shù)據(jù)范圍如何改變“最優(yōu)解”的定義數(shù)據(jù)范圍至少包含以下幾個維度每個維度都直接影響選型維度含義示例影響的算法選擇值域上界 U元素最大可能取值0 ~ 10^5、0 ~ 2^31-1決定能否用數(shù)組直接定址連續(xù)性值域是否基本連續(xù)用戶ID是否從0遞增分配決定數(shù)組是否浪費(fèi)空間密集程度實際出現(xiàn)的元素數(shù)量 vs 值域大小稀疏與密集數(shù)組 vs 哈希表重復(fù)程度是否有大量重復(fù)元素狀態(tài)枚舉值計數(shù)排序 vs 比較排序偏移量最小值是否遠(yuǎn)大于0時間戳、ID從大數(shù)開始是否做映射、平移分布形態(tài)均勻、偏斜、冪律長尾數(shù)據(jù)基數(shù)排序 vs 計數(shù)排序舉一個直觀類比假設(shè)你要給一萬個盒子貼上對應(yīng)編號的標(biāo)簽每個盒子上的編號從 1 到 10000。如果你提前知道“編號范圍就是 1 到 10000”最蠢也最有效的辦法是準(zhǔn)備一萬個空位看見幾號盒子就放到幾號位子上如果你不知道編號范圍就得把所有盒子排成一排一個個比較交換排序。前者就是“范圍已知”的威力——你不需要通過互相比較來推斷位置而是直接把“值”當(dāng)成“位置”。理解了這個前提下面就可以進(jìn)入實際操作層面的拆解了。2. 四個高頻場景的選型拆解排序、查找、去重、素數(shù)處理范圍信息對算法選型的影響在排序、查找、去重、素數(shù)這四個場景里體現(xiàn)得最充分。我分別把它們的決策邏輯講透。2.1 排序場景計數(shù)排序碾壓快排的邊界在哪里計數(shù)排序的思路本質(zhì)上是“用空間換時間”它把數(shù)據(jù)本身當(dāng)作數(shù)組下標(biāo)先統(tǒng)計每個值出現(xiàn)多少次再按值從小到大把元素回填。它成立的條件很苛刻但也很明確元素必須是非負(fù)整數(shù)值域 U 不能太大而且你能容忍排序后的元素只是數(shù)值有序大多時候這足夠了。當(dāng) U 遠(yuǎn)小于 n 時計數(shù)排序幾乎無敵當(dāng) U 和 n 同量級比如 n 10^7、U 10^7那么 O(n U) 和 O(n log n) 差別不大這時反而要考慮內(nèi)存占用和常數(shù)因子。一個實際的選擇標(biāo)準(zhǔn)可以寫成U ≤ 10^7內(nèi)存允許 4U 字節(jié)int 數(shù)組時優(yōu)先考慮計數(shù)排序如果數(shù)據(jù)中有負(fù)數(shù)先做平移把最小值變?yōu)?如果不只是簡單排序還需要按其他鍵二次排序改用基數(shù)排序或“計數(shù)排序穩(wěn)定歸并”?；鶖?shù)排序值得多說一句。它是計數(shù)排序的推廣把整數(shù)按位拆成多個關(guān)鍵字每一位分別做一次穩(wěn)定的計數(shù)排序。比如 32 位整數(shù)可以按 8 位一組分成 4 輪。這樣即使 U 很大接近 2^32只要數(shù)據(jù)本身分布均勻也能在 O(n × 位數(shù)/組大小) 內(nèi)排完大約就是 O(4n)。所以面對 0 到 2^32-1 的大范圍整數(shù)排序基數(shù)排序是比快速排序更貼近“工程最優(yōu)”的選擇之一。這里有一個需要警惕的誤區(qū)有些資料說“計數(shù)排序適合小范圍”但沒定義“小”到底是多少。在很多競賽和面試場景里值域 10^6 以下才算“小”但在真實系統(tǒng)里如果內(nèi)存很充裕10^8 也能硬上需要約 400MB 內(nèi)存。我曾經(jīng)在某數(shù)據(jù)分析腳本里就真用 10^8 的 int 數(shù)組做過一次計數(shù)統(tǒng)計明顯比跑外部排序快得多——前提是這臺機(jī)器內(nèi)存夠大腳本是短生命周期的。2.2 查找場景二分、哈希、還是直接數(shù)組下標(biāo)查找問題里“范圍已知”的價值被很多人低估了。當(dāng)數(shù)據(jù)范圍是有限的連續(xù)整數(shù)時最猛的查找結(jié)構(gòu)其實是一個普通的數(shù)組。假設(shè)你有一個系統(tǒng)用戶ID從 0 遞增分配最多 10^7 個用戶需要根據(jù) ID 快速查到用戶信息。此時直接開一個大小為 10^7 的數(shù)組下標(biāo)就是 ID# 建立直接按下標(biāo)存 users [None] * MAX_USER_ID def add_user(uid, info): users[uid] info def get_user(uid): return users[uid]查找復(fù)雜度為 O(1)而且沒有任何哈希沖突、沒有鏈表指針跳轉(zhuǎn)、沒有緩存缺失問題。相比之下哈希表雖然理論也是 O(1)但它需要計算哈希、處理沖突、可能觸發(fā)擴(kuò)容常數(shù)因子比數(shù)組直接定址大不少紅黑樹和跳表理論 O(log n)更是差了一個數(shù)量級。二分查找則適合另一種場景數(shù)據(jù)本身已經(jīng)有序但你不知道數(shù)據(jù)的分布密度只知道范圍。比如你要在一個已排序的數(shù)組中查找某個值二分查找完全不關(guān)心值域大小只關(guān)心元素個數(shù) n這是它的天然優(yōu)勢。所以查找場景的決策邏輯大致如下值是連續(xù)或接近連續(xù)的整數(shù)且下界不大 → 直接數(shù)組定址值域稀疏但已知上下界 → 先離散化再用二分或哈希值域未知、數(shù)據(jù)靜態(tài)有序 → 二分查找值域未知、數(shù)據(jù)動態(tài)插入刪除 → 哈希表或平衡樹。我不是說哈希表不好哈希表在很多場景確實是全能選手。但“范圍已知”這個信息經(jīng)常能把哈希表降級成一個更簡單的數(shù)組省掉一堆隱形成本。尤其是高并發(fā)讀取場景數(shù)組定址的局部性好CPU 緩存友好性能優(yōu)勢非常明顯。2.3 去重場景位圖與布爾數(shù)組的空間賬去重問題的本質(zhì)是“判斷某個值是否出現(xiàn)過”。如果值的范圍已知最簡單的辦法是布爾數(shù)組甚至位圖。給一個具體例子。某系統(tǒng)需要過濾 10^9 條請求里的重復(fù)設(shè)備編號設(shè)備編號是 32 位非負(fù)整數(shù)最大值約 4×10^9——這個范圍太大直接開 int 數(shù)組需要 16GB顯然不現(xiàn)實。但如果換一個角度我們不關(guān)心某個編號出現(xiàn)了多少次只關(guān)心“是否出現(xiàn)過”就可以用位圖來表示每個編號只占 1 bit4×10^9 個編號對應(yīng)約 500MB。雖然也不小但已經(jīng)比 int 數(shù)組省了 32 倍配合分段加載、多線程處理很多場景是可行的。如果范圍再小一些比如設(shè)備編號實際是 MAC 地址后 24 位0 ~ 2^24-1約 1600 萬個取值位圖只需要 2MB。直接用 bitset 或手工字節(jié)數(shù)組都能輕松裝進(jìn)內(nèi)存。// 位圖去重假設(shè)值域為 [0, MAX_VAL) vectoruint8_t bitmap((MAX_VAL 7) / 8, 0); bool markIfFirstSeen(uint32_t val) { uint32_t byteIdx val 3; uint8_t bitMask 1 (val 7); bool first !(bitmap[byteIdx] bitMask); bitmap[byteIdx] | bitMask; return first; }哈希 Set 也能去重但它有兩個問題內(nèi)存占用大每個元素除了值本身還有哈希桶、節(jié)點指針、負(fù)載因子預(yù)留空間而且哈希碰撞后還會退化。所以當(dāng)范圍可控時位圖在內(nèi)存和時間上都是更優(yōu)選擇。去重場景的選型邏輯可以總結(jié)為值域 ≤ 10^7直接用布爾數(shù)組約 10MB值域 ≤ 10^9考慮位圖約 125MB還是要評估內(nèi)存預(yù)算值域 10^9 且實際元素數(shù)量少 → 哈希 Set 或布隆過濾器允許誤判、且數(shù)據(jù)量極大 → 布隆過濾器它本質(zhì)上也依賴“范圍預(yù)估”來設(shè)定位數(shù)組大小和哈希函數(shù)個數(shù)。布隆過濾器這里尤其值得展開它需要的位數(shù)組大小依賴于你預(yù)估的元素數(shù)量 n 和可接受的誤判率 p。公式是 m ≈ -(n × ln p) / (ln 2)^2。這不就是“根據(jù)已知數(shù)據(jù)范圍預(yù)估規(guī)模選擇參數(shù)”的典型例子嗎范圍估計得越準(zhǔn)布隆過濾器就越省內(nèi)存且誤判可控。2.4 素數(shù)處理大范圍區(qū)間篩的偏移存儲技巧素數(shù)問題看起來和“數(shù)據(jù)范圍選型”沒直接關(guān)系但我做某次數(shù)論相關(guān)需求時踩過坑這里必須分享一下。如果需求是求區(qū)間 [L, R] 內(nèi)的所有素數(shù)L 和 R 可能很大比如 L 10^9R 10^9 10^7。此時你沒法直接開一個大小為 R1 的布爾數(shù)組來篩——那要 1GB 以上空間。但區(qū)間長度 R - L 1 只有 10^7是可以輕松放進(jìn)內(nèi)存的。做法是埃氏篩的“區(qū)間偏移”先用普通埃氏篩把不超過 sqrt(R) 的素數(shù)全部找出來再用這些素數(shù)去篩 [L, R] 區(qū)間內(nèi)合數(shù)但數(shù)組下標(biāo)只需要從 0 到 R-Lvectorbool isPrime(R - L 1, true); // 先用經(jīng)典篩法得到所有 sqrt(R) 的素數(shù) primes for (int p : primes) { // 找到 [L, R] 中第一個能被 p 整除的數(shù) long long start max((long long)p * p, ((L p - 1) / p) * p); for (long long j start; j R; j p) { if (j ! p) isPrime[j - L] false; } }思路核心就是把值域范圍從 [0, R] 偏移成 [0, R-L]也就是“已知區(qū)間長度而不是已知絕對最大值”。這類偏移技巧在算法競賽和工程里都能見到本質(zhì)上是讓你不要被問題表面的大數(shù)值嚇到——多問一句“我關(guān)心的范圍到底是從哪到哪、跨度有多大”選型思路就會完全不一樣。類似的還有線性篩歐拉篩它在需要頻繁查詢前綴素數(shù)個數(shù)、或需要維護(hù)每個數(shù)的最小質(zhì)因子時更好用但代價是需要完整表。如果范圍已知且不大比如 U ≤ 10^7線性篩是首選范圍很大但只查某個區(qū)間區(qū)間篩配合偏移才是正解。3. 范圍已知不等于一切稀疏、偏移、大值域的邊界處理上一章講的是“范圍已知帶來的紅利”實際操作中更常見的卻是“范圍似乎知道了但沒那么簡單”。我把最常見的邊界情況列一下。3.1 稀疏范圍是陷阱值域大而實際元素少最常見的翻車場景是系統(tǒng)文檔告訴你“編號范圍是 1 到 10^9”于是你想開一個 10^9 的數(shù)組然后發(fā)現(xiàn)內(nèi)存直接爆炸。但你仔細(xì)看看數(shù)據(jù)實際出現(xiàn)的編號總共只有 10^4 個——這就是稀疏范圍。在稀疏范圍面前直接定址不可行應(yīng)該轉(zhuǎn)向離散化把所有出現(xiàn)過的值收集起來排序去重后映射成 0 到 m-1 的緊湊下標(biāo)再用數(shù)組或樹狀數(shù)組處理。比如你要對一堆區(qū)間做覆蓋次數(shù)統(tǒng)計編號是 10^9 量級的離散點。開數(shù)組不可能但把這些點離散化后問題規(guī)模就變成“實際點數(shù) m”所有基于范圍下標(biāo)的算法都能繼續(xù)用vectorint allVals originalVals; sort(allVals.begin(), allVals.end()); allVals.erase(unique(allVals.begin(), allVals.end()), allVals.end()); // 之后要查某個 val先二分定位lower_bound(allVals.begin(), allVals.end(), val)這里“范圍已知”的信息并沒有失效而是換了一種用法范圍決定了你能預(yù)判離散化后 m 的大小上限進(jìn)而決定是選樹狀數(shù)組還是線段樹、是選普通數(shù)組還是哈希。離散化后的查找用二分 O(log m)也可以再套哈希 O(1)如果 m 不超過 10^6甚至可以直接開一個大小為 m 的數(shù)組配合“反離散化映射”。我個人的經(jīng)驗是在做任何依賴“值域大小 U”的算法之前先統(tǒng)計“實際互異元素數(shù)量 m”。如果 m 遠(yuǎn)小于 U走離散化如果 m 和 U 同量級且 U 可控才考慮直接開數(shù)組。3.2 負(fù)數(shù)與起始偏移讓下標(biāo)從0開始的三種映射方式已知范圍是從負(fù)數(shù)開始或者最小值遠(yuǎn)大于 0 時不能直接使用原始值作為數(shù)組下標(biāo)。處理辦法很簡單建立從“原始值”到“數(shù)組下標(biāo)”的映射常見有三種。第一種是整體平移。如果范圍是 [-10^5, 10^5]把所有值加上 10^5變成 [0, 2×10^5]再開數(shù)組。這種方式最簡單但前提是范圍不大否則平移只是把問題延后內(nèi)存照樣過大。第二種是取?；蚬Ｓ成?。適用于大值域但稀疏的情況本質(zhì)上是哈希表不保證下標(biāo)連續(xù)。第三種是排序后二分定位。也就是前面說的離散化適合值域范圍大、但實際值集合固定且數(shù)量不多的查詢場景。這三種方式的選型判斷依據(jù)還是回到第一張表里那幾個維度范圍跨度、連續(xù)性、實際元素數(shù)量。如果跨度小且連續(xù)平移開數(shù)組最優(yōu)跨度大且稀疏離散化加二分動態(tài)插入且無法排序哈希。一個我曾經(jīng)忽略的細(xì)節(jié)做平移時一定要確認(rèn)映射后的最大值不超過數(shù)組邊界。比如值是 [10^6, 10^6 10^4]平移量是 10^6但有些人只平移了最小值卻忘了數(shù)組長度等于“最大值減最小值加一”導(dǎo)致越界訪問。測試時數(shù)據(jù)不靠邊界根本發(fā)現(xiàn)不了一旦上線就偶發(fā)崩潰非常難排查。3.3 分布不均時基數(shù)排序比計數(shù)排序更穩(wěn)計數(shù)排序在值域很小但分布極不均勻時有一個隱藏問題回填階段需要把所有值域遍歷一遍哪怕絕大多數(shù)值從來沒有出現(xiàn)過。如果 U 10^8n 10^6那么 O(n U) 實際約等于 1.01 億次操作大部分時間浪費(fèi)在空轉(zhuǎn)的 for 循環(huán)上。雖然也不算慢但內(nèi)存開銷已經(jīng)不小400MB 左右的 int 數(shù)組。此時可以考慮基數(shù)排序的變體按二進(jìn)制位分組做 LSD 排序。32 位整數(shù)按 8 位一桶只需 4 輪每輪 O(n)總共 O(4n)。它不要求值域連續(xù)只依賴于位寬。實測中當(dāng)數(shù)據(jù)非常集中比如所有數(shù)都在 0 到 2^20 附近時基數(shù)排序依然穩(wěn)定而計數(shù)排序則會因為 U 大而吃虧或者因為 U 小而先要掃描全范圍。還有一個更實用的組合先根據(jù)高位做一次粗分桶把數(shù)據(jù)拆到若干個區(qū)間里區(qū)間內(nèi)部如果值域跨度已經(jīng)很小再對每個區(qū)間單獨(dú)做計數(shù)排序。這種“桶排序 計數(shù)排序”的思路在很多大數(shù)據(jù)排序系統(tǒng)里都能見到本質(zhì)就是利用數(shù)據(jù)范圍的層次性——外層看范圍分桶內(nèi)層看區(qū)間跨度再細(xì)化。3.4 時間與內(nèi)存的權(quán)衡bitset、壓縮與分段處理當(dāng)范圍 U 很大但你又想保留“范圍直接定址”的好處時內(nèi)存會成為瓶頸。這時有幾個工程手段值得掌握。位壓縮前面提過值域 U 的布爾數(shù)組至少 U 字節(jié)位圖只要 U/8 字節(jié)。例如 U 10^8布爾數(shù)組 100MB位圖 12.5MB差距非常明顯。分段處理如果一次性裝不下可以考慮按值域分段。比如值域 0 到 10^9我把范圍切成 100 段每段長度 10^7每次只加載一段到內(nèi)存處理處理完寫回結(jié)果再換下一段。這種方式犧牲了隨機(jī)訪問的便利性但能把“范圍已知”的優(yōu)勢從內(nèi)存受限場景中拯救出來。壓縮編碼當(dāng)數(shù)據(jù)的值域連續(xù)但分布極不均勻時可以用差值編碼、前綴和編碼等方式壓縮存儲。這已經(jīng)進(jìn)入數(shù)據(jù)結(jié)構(gòu)的深層定制了一般只在存儲成本極高時才會考慮。我的建議是先別急著上壓縮先用位圖和分段扛一扛絕大多數(shù)場景已經(jīng)夠用。4. 從一次翻車經(jīng)歷談選型前必問的六個問題講完了原理我想用一段真實踩坑記錄收尾。某次我負(fù)責(zé)一個內(nèi)部統(tǒng)計系統(tǒng)需求是給海量請求按來源IP段聚合計數(shù)。IP是IPv4四個字節(jié)我當(dāng)時想當(dāng)然地以為“IPv4范圍就是 0 到 2^32-1均勻分布”于是一開始就準(zhǔn)備了一張大小為 2^32 的數(shù)組算一下 16GB直接超了內(nèi)存預(yù)算。后來又改成哈希表但因為 IP 段極不均勻地集中在少數(shù)幾個C段哈希表碰撞率很高性能又不行。最后我做了兩件事先用采樣統(tǒng)計出實際出現(xiàn)的IP段數(shù)量再把“IP地址范圍”轉(zhuǎn)換成“CIDR前綴范圍”按前綴長度分層處理。最終方案是高頻前綴用緊湊數(shù)組直接定址低頻稀疏部分用離散化加二分。整體內(nèi)存不到原來的十分之一性能還比哈希表快了三倍。這次經(jīng)歷讓我總結(jié)出選型前必問的六個問題也推薦給你問題目的不回答的后果值的確定上下界是什么判斷能否直接定址內(nèi)存浪費(fèi)或越界值域跨度多大實際出現(xiàn)多少互異值判斷稀疏程度直接開數(shù)組爆內(nèi)存值是連續(xù)還是離散分布是否均勻選擇計數(shù)排序、基數(shù)排序還是桶排序空轉(zhuǎn)/碰撞是否存在偏移、負(fù)數(shù)、大起始值決定是否平移/離散化下標(biāo)越界是否需要穩(wěn)定排序、隨機(jī)訪問、內(nèi)存受限決定工程約束算法正確但工程不可用最壞情況下的值域邊界是否可能突破預(yù)估決定是否留冗余上線后偶發(fā)崩潰這六個問題看著簡單但真到項目里很多人是在寫完代碼之后才開始考慮的順序反了。正確做法是寫算法前先做 5 分鐘的數(shù)據(jù)分析哪怕是粗略估算也遠(yuǎn)比憑感覺選結(jié)構(gòu)要可靠。選完算法之后還有一步容易被漏掉用多組不同規(guī)模的數(shù)據(jù)做基準(zhǔn)測試而不是只看理論復(fù)雜度。理論分析只告訴我們增長趨勢常數(shù)因子、緩存行為、內(nèi)存分配開銷只有實測才能暴露。具體做法我一般是這樣先把數(shù)據(jù)規(guī)模從小到大各測一輪比如 n 10^4、10^5、10^6、10^7同一規(guī)模下再測分布極不均勻的情況對比時間時順帶記錄內(nèi)存峰值如果理論曲線和實測曲線偏離超過一個數(shù)量級回頭檢查是不是忽略了對數(shù)項或線性掃描項。還是拿時間戳那個例子說。當(dāng)時我把直接定址數(shù)組換成“哈希 紅黑樹”理論上排序和聚合看起來都嚴(yán)謹(jǐn)?shù)珜崪y下來數(shù)組版本因為緩存友好反而快了接近一個數(shù)量級。這個現(xiàn)象用大O符號很難解釋但在真實硬件上就是那么殘酷——常量因子、內(nèi)存局部性往往比漸進(jìn)復(fù)雜度更能決定一個系統(tǒng)的最終性能。而“范圍已知”恰好能讓你在更多場景里選擇那個常量極小、局部性極好的數(shù)組方案。最后一個我個人的實操習(xí)慣在代碼注釋里把“為什么選這個算法”寫下來。記錄數(shù)據(jù)范圍是多少、為什么認(rèn)為范圍可控、如果范圍翻十倍應(yīng)該怎么切換方案。這看起來像小事但對后來維護(hù)代碼的人來說包括三個月后的自己這比寫十行“這段代碼實現(xiàn)了XXX”有用得多。算法選型不是一錘子買賣數(shù)據(jù)范圍可能隨著業(yè)務(wù)增長而變化那時就是重新評估算法的時候。以上就是我根據(jù)已知數(shù)據(jù)范圍做算法選型的完整思路和實操經(jīng)驗。信息密度確實不低但如果你在真實項目中遇到確定值域的數(shù)據(jù)回來看一眼這六個問題應(yīng)該能少走不少彎路。