最近點(diǎn)對(duì)問(wèn)題Closest Pair of Points是我當(dāng)年學(xué)算法時(shí)印象最深的一道題平面上給一堆點(diǎn)找出距離最近的兩個(gè)點(diǎn)。暴力解法分分鐘想到但數(shù)據(jù)量一上去就卡死。分治法的處理思路極其經(jīng)典配合畫(huà)圖理解后整個(gè)證明和實(shí)現(xiàn)都會(huì)變得異常清晰。這篇文章我不僅會(huì)把分治法講透還會(huì)用一套具體數(shù)據(jù)把每一步的圖都畫(huà)出來(lái)包括劃分、遞歸、合并、候選區(qū)域這些關(guān)鍵環(huán)節(jié)看完你就能完整復(fù)現(xiàn)整個(gè)算法。1. 最近點(diǎn)對(duì)問(wèn)題從暴力到分治的演進(jìn)1.1 問(wèn)題定義平面上找距離最近的兩個(gè)點(diǎn)題目本身不復(fù)雜。假設(shè)平面上有 n 個(gè)點(diǎn)每個(gè)點(diǎn)用坐標(biāo) (x, y) 表示要求找出歐幾里得距離最近的一對(duì)點(diǎn)。注意是點(diǎn)到點(diǎn)之間的直線距離d sqrt((x1-x2)2 (y1-y2)2)這個(gè)問(wèn)題的應(yīng)用場(chǎng)景比我最初想的多。比如地理位置聚類(lèi)里要找出距離最近的兩個(gè)基站碰撞檢測(cè)里要找出空間中距離最近的兩個(gè)對(duì)象還有圖像處理中的特征點(diǎn)匹配第一步往往都是找最近鄰居。很多更大規(guī)模的問(wèn)題會(huì)把最近點(diǎn)對(duì)當(dāng)作一個(gè)子過(guò)程反復(fù)調(diào)用所以這個(gè)基礎(chǔ)算法能不能跑得快直接影響整個(gè)系統(tǒng)的性能。我剛學(xué)的時(shí)候第一反應(yīng)就是暴力法把所有點(diǎn)兩兩組合都算一遍距離記錄最小值。兩層循環(huán)搞定代碼簡(jiǎn)單到不用思考。但問(wèn)題在于復(fù)雜度。n 個(gè)點(diǎn)兩兩組合有 C(n,2) n(n-1)/2 種情況時(shí)間復(fù)雜度是 O(n2)。n 等于 1000 的時(shí)候大約要算 50 萬(wàn)次距離n 等于 10 萬(wàn)的時(shí)候就是 50 億次。這個(gè)增長(zhǎng)趨勢(shì)會(huì)迅速擊穿計(jì)算資源。實(shí)際項(xiàng)目中如果點(diǎn)集規(guī)模上了萬(wàn)O(n2) 的暴力解法基本就是不可用的必須找更聰明的辦法。1.2 為什么暴力解會(huì)卡死規(guī)模增長(zhǎng)的速度我拿一組實(shí)際數(shù)據(jù)感受一下。假設(shè)一秒鐘能算 1000 萬(wàn)次距離已經(jīng)是相當(dāng)樂(lè)觀的估算不同規(guī)模的點(diǎn)集會(huì)呈現(xiàn)這樣的耗時(shí)點(diǎn)數(shù)量 n兩兩組合數(shù)量估算耗時(shí)1,000約 50 萬(wàn)0.05 秒10,000約 5000 萬(wàn)5 秒100,000約 50 億500 秒1,000,000約 5000 億50000 秒n 從 1 千漲到 100 萬(wàn)點(diǎn)數(shù)量只多了 1000 倍耗時(shí)卻多了約 100 萬(wàn)倍。這就是 O(n2) 的可怕之處。而且這還只是距離計(jì)算還沒(méi)算上距離比較、臨時(shí)變量維護(hù)這些開(kāi)銷(xiāo)。真實(shí)場(chǎng)景里點(diǎn)動(dòng)輒幾十萬(wàn)個(gè)暴力法基本不可行。所以問(wèn)題的關(guān)鍵變成了能不能把復(fù)雜度壓到 O(n log n) 甚至 O(n)分治法正好能做到 O(n log n)而且思路非常符合直覺(jué)就是大事化小、小事化了。2. 分治法的整體設(shè)計(jì)與畫(huà)圖拆解2.1 三步走劃分、遞歸、合并分治法處理最近點(diǎn)對(duì)的標(biāo)準(zhǔn)流程可以總結(jié)成三步。第一步劃分。把所有點(diǎn)按照 x 坐標(biāo)排序然后取中位數(shù)用一條垂直于 x 軸的線把點(diǎn)集分成左半和右半兩部分兩邊點(diǎn)數(shù)盡量均衡。第二步遞歸。分別對(duì)左半部分和右半部分遞歸地求解最近點(diǎn)對(duì)得到左半內(nèi)部的最近距離 dL 和右半內(nèi)部的最近距離 dR。遞歸出口是區(qū)間里只有一個(gè)點(diǎn)或兩個(gè)點(diǎn)一個(gè)點(diǎn)沒(méi)有距離直接返回?zé)o窮大兩個(gè)點(diǎn)直接算它們之間的距離。第三步合并。這是最關(guān)鍵的步驟。全局最近點(diǎn)對(duì)除了可能出現(xiàn)在左半內(nèi)部或右半內(nèi)部還有一種特殊情況一個(gè)點(diǎn)在左半一個(gè)點(diǎn)在右半它們跨越了分割線。這類(lèi)跨線點(diǎn)對(duì)需要在合并時(shí)專(zhuān)門(mén)處理。合并的目標(biāo)就是找出所有跨線點(diǎn)對(duì)中的最近距離然后跟 dL、dR 比較取最小值。這個(gè)三步走看起來(lái)平淡無(wú)奇但合并步驟里藏著一個(gè)幾乎所有初學(xué)者都會(huì)忽略的優(yōu)化點(diǎn)跨線點(diǎn)對(duì)到底要檢查哪些點(diǎn)如果無(wú)腦把所有左半點(diǎn)和所有右半點(diǎn)兩兩比較那復(fù)雜度又回到 O(n2)分治就白做了。2.2 用一張圖畫(huà)清分治過(guò)程理解分治最好的方式就是畫(huà)圖。我用一組具體數(shù)據(jù)演示點(diǎn)集一共 8 個(gè)點(diǎn)隨便編一組坐標(biāo)但特意設(shè)計(jì)成跨線點(diǎn)對(duì)會(huì)成為最終答案這樣合并步驟的意義才能體現(xiàn)出來(lái)。點(diǎn)集分布示意 y 31 L3 30 L1 28 L2 ... 16 R3 15 R1 13 R2 8 6 4 B 3 L4 ----------------------------------------------------------- x 1 2 3 4 5 6 7 8 9 ... 20 21 228 個(gè)點(diǎn)按 x 坐標(biāo)排序后是編號(hào)坐標(biāo)左/右半?yún)^(qū)L1(1, 30)左半L2(2, 28)左半L3(3, 31)左半L4(5, 3)左半B(6, 4)右半R1(20, 15)右半R2(21, 13)右半R3(22, 16)右半初始狀態(tài)按 x 坐標(biāo)排序后取中間位置把點(diǎn)集切成左右各 4 個(gè)。分割線畫(huà)在 x 5.5 左右也就是 L4 和 B 之間。分割示意 y 31 L3 30 L1 28 L2 ... 16 R3 15 R1 13 R2 4 B 3 L4 |← 左半4個(gè)點(diǎn) →|← 右半4個(gè)點(diǎn) →| x5.5后面整個(gè)算法的推演我都會(huì)基于這張圖來(lái)講。你看到的是先豎著切一刀左右各自找最短再檢查跨線區(qū)域這套邏輯配上圖就完全不會(huì)亂。3. 合并步驟真正的大 Boss3.1 strip 區(qū)域哪些點(diǎn)值得檢查合并時(shí)的樸素做法是把左半所有點(diǎn)和右半所有點(diǎn)都兩兩算一遍。但這顯然不行。仔細(xì)想想就會(huì)發(fā)現(xiàn)大部分跨線點(diǎn)對(duì)根本不可能成為最優(yōu)解。已知當(dāng)前最佳的左右內(nèi)部距離是 d min(dL, dR)。如果跨線點(diǎn)對(duì)的距離要小于 d那么這兩個(gè)點(diǎn)的 x 坐標(biāo)都不能離分割線太遠(yuǎn)。具體來(lái)說(shuō)任何一個(gè)點(diǎn)如果它的 x 坐標(biāo)與分割線的水平距離已經(jīng)大于等于 d那它跟對(duì)面任何一個(gè)點(diǎn)的距離都不可能小于 d。因?yàn)闅W幾里得距離必然大于等于水平方向的差距。所以真正值得檢查的候選區(qū)域是以分割線為中心、寬度為 2d 的一條豎直帶狀區(qū)域通常叫 strip。分割線左邊 d 寬右邊 d 寬。strip 區(qū)域示意 y 31 L3 30 L1 28 L2 ... 16 R3 15 R1 13 R2 4 B 3 L4 | | | |← d →| | strip左邊界 分割線 strip右邊界 x5.5-d x5.5 x5.5dstrip 區(qū)域之外的點(diǎn)直接忽略因?yàn)樗鼈冊(cè)谒椒较蛏暇筒粔蚋瘛＿@個(gè)剪枝讓候選點(diǎn)數(shù)量大幅減少。但問(wèn)題還沒(méi)完全解決如果點(diǎn)分布很密strip 里可能依然有大量點(diǎn)全兩兩比較還是災(zāi)難。3.2 在 strip 內(nèi)按 y 坐標(biāo)排序滑動(dòng)窗口的思想strip 內(nèi)的點(diǎn)不能繼續(xù)用 x 方向來(lái)剪枝了因?yàn)樗鼈?x 方向都在分割線附近。這里換一個(gè)思路把 strip 內(nèi)的所有點(diǎn)按 y 坐標(biāo)排序。排序之后固定當(dāng)前點(diǎn) p只需要檢查排在 p 后面的那些點(diǎn) q。如果 p 和 q 的 y 坐標(biāo)差已經(jīng)大于等于 d那兩點(diǎn)距離必然大于等于 d直接停止檢查后面的點(diǎn)。因?yàn)?y 坐標(biāo)遞增后面的點(diǎn)只會(huì)離得更遠(yuǎn)。這個(gè)思路非常像滑動(dòng)窗口對(duì)每個(gè)點(diǎn)只在一個(gè)高度為 d 的窗口里向后看。strip 內(nèi)按 y 排序后的檢查示意 y 坐標(biāo)升序排列 (5,3) ← p1 (6,4) ← p2 → 與 p1 的 y 差 1 d需要比較 如果某點(diǎn)的 y 與 p1 的差超過(guò) d就跳過(guò)。這樣一來(lái)每個(gè)點(diǎn)不會(huì)跟 strip 里所有點(diǎn)比較最多只會(huì)跟 y 坐標(biāo)差距小于 d 的那些點(diǎn)比較。那么接下來(lái)還有一個(gè)關(guān)鍵問(wèn)題在一個(gè)高度為 d 的窗口里最多可能有多少個(gè)點(diǎn)如果這個(gè)數(shù)量是常數(shù)整個(gè)合并步驟就能做到 O(n)。3.3 幾何證明的畫(huà)圖講解為什么最多只能檢查常數(shù)個(gè)點(diǎn)這個(gè)證明是整個(gè)分治法最近點(diǎn)對(duì)里最精彩的部分。想象一個(gè)寬 2d、高 d 的矩形p 點(diǎn)在這個(gè)矩形的左下角附近矩形內(nèi)部包含了所有可能與 p 距離小于 d 的候選點(diǎn)。2d × d 矩形內(nèi)的劃分示意 --------------------------- | | | | | 格 A | 格 B | 格 C | | | | | --------------------------- | p所在 | 格 E | 格 F | | 格 D | | | ---------------------------把這個(gè)矩形切成 2 行 3 列共 6 個(gè)小矩形。每個(gè)小矩形的寬是 2d/3高是 d/2。算一下對(duì)角線長(zhǎng)度sqrt((2d/3)2 (d/2)2) d × sqrt(4/9 1/4) d × sqrt(16/36 9/36) d × sqrt(25/36) 5d/6對(duì)角線約等于 0.833d嚴(yán)格小于 d。這意味著什么如果一個(gè)格子里面放了兩個(gè)點(diǎn)它們之間的距離會(huì)被限制在這個(gè)格子的對(duì)角線以內(nèi)也就是必須小于 d。但我們知道 d 已經(jīng)是左右兩個(gè)子區(qū)域內(nèi)找出來(lái)的最短距離了整個(gè)平面上不可能再有距離小于 d 的點(diǎn)對(duì)存在否則左右遞歸早就發(fā)現(xiàn)了。所以每個(gè)小矩形里最多只能有 1 個(gè)點(diǎn)。6 個(gè)小矩形加起來(lái)最多 6 個(gè)點(diǎn)再加上 p 點(diǎn)自己也不超過(guò) 7 個(gè)點(diǎn)。就算不同教材畫(huà)法有差異有的切成 8 個(gè)小正方形核心結(jié)論都一樣這個(gè)區(qū)域內(nèi)點(diǎn)的數(shù)量是常數(shù)。所以每個(gè)點(diǎn)只需要向后檢查固定數(shù)量的幾個(gè)點(diǎn)就夠了不需要看完整條 strip。4. 手把手畫(huà)圖演示完整流程4.1 遞歸過(guò)程的畫(huà)圖推演回到我設(shè)計(jì)的那組數(shù)據(jù)。8 個(gè)點(diǎn)按 x 排序后先分成左半和右半然后兩邊各自遞歸。遞歸樹(shù)如下全部 8 個(gè)點(diǎn) / \ 左半 4 個(gè)點(diǎn) 右半 4 個(gè)點(diǎn) / \ / \ (1,30),(2,28) (3,31),(5,3) (6,4),(20,15) (21,13),(22,16) d√5 d√788 d√317 d√10 \ / \ / 左半合并 d√5 右半合并 d√5 \ / 全局合并跨線候選 d√2逐個(gè)看。左半 4 個(gè)點(diǎn)是 (1,30)、(2,28)、(3,31)、(5,3)。繼續(xù)劃分(1,30) 和 (2,28) 一組距離是 sqrt((1-2)2(30-28)2) sqrt(14) √5(3,31) 和 (5,3) 一組距離是 sqrt(4784) √788。左半合并時(shí)d 取 min(√5, √788) √5strip 區(qū)域?qū)挾?2√5里面包含 (1,30)、(2,28)、(3,31)進(jìn)一步檢查后仍然沒(méi)有更小值所以左半內(nèi)部最近距離就是 √5。右半 4 個(gè)點(diǎn)是 (6,4)、(20,15)、(21,13)、(22,16)。(6,4) 和 (20,15) 距離 sqrt(196121) √317(21,13) 和 (22,16) 距離 sqrt(19) √10。右半合并時(shí) d √10strip 內(nèi)按 y 排序后有 (21,13)、(20,15)、(22,16)其中 (20,15) 和 (21,13) 的距離是 sqrt(14) √5比 √10 更小于是右半最近距離更新成 √5。此時(shí)全局上界 d min(√5, √5) √5。4.2 合并過(guò)程的畫(huà)圖推演跨線點(diǎn)對(duì)登場(chǎng)合并左半和右半時(shí)分割線取 x 5.5當(dāng)前最優(yōu)距離 d √5 ≈ 2.236。strip 區(qū)域的范圍就是[5.5 - 2.236, 5.5 2.236] [3.264, 7.736]所有點(diǎn)里x 坐標(biāo)落在這個(gè)區(qū)間的只有兩個(gè)(5,3) 和 (6,4)。其他點(diǎn)要么在 strip 左邊要么在右邊直接排除。全局合并時(shí)的 strip y 4 B 3 L4 |← d2.236 →|← d2.236 →| x3.264 x5.5 x7.736 strip 內(nèi)只有兩個(gè)點(diǎn) (5,3) 和 (6,4)strip 內(nèi)按 y 排序后依然是 (5,3)、(6,4)。兩個(gè)點(diǎn)之間 y 坐標(biāo)差 1小于 d所以必須計(jì)算距離sqrt((5-6)2 (3-4)2) sqrt(11) √2 ≈ 1.414√2 小于當(dāng)前全局上界 √5于是答案更新為 √2。最終最近點(diǎn)對(duì)就是跨線的 (5,3) 和 (6,4)。這組數(shù)據(jù)特別適合演示分治的合并威力左半內(nèi)部和右半內(nèi)部各自的最短距離都是 √5但全局最短卻是跨線的 √2。如果只看左右兩半的結(jié)果永遠(yuǎn)發(fā)現(xiàn)不了這個(gè)更優(yōu)答案。這也是為什么合并步驟絕不能省略的原因。4.3 畫(huà)圖理解為什么合并不會(huì)漏掉答案很多第一次學(xué)的人都會(huì)擔(dān)心strip 里只檢查這么點(diǎn)候選會(huì)不會(huì)把正確答案漏掉我當(dāng)時(shí)也有這個(gè)懷疑。畫(huà)一遍圖之后其實(shí)就清楚了。假設(shè)真正的最優(yōu)跨線點(diǎn)對(duì)是 a 和 b距離小于當(dāng)前 d。a 和 b 分別在分割線兩側(cè)它們每個(gè)點(diǎn)到分割線的水平距離都必然小于它們之間的距離也就必然小于 d。所以 a 和 b 都一定在 strip 區(qū)域內(nèi)不會(huì)被剪枝剪掉。這是合并步驟正確性的第一重保障。第二重保障是 y 坐標(biāo)窗口。a 和 b 的 y 坐標(biāo)差不會(huì)超過(guò)它們的距離也就小于 d。所以在按 y 排序后的序列里a 和 b 一定落在同一個(gè)高度為 d 的窗口內(nèi)檢查 a 時(shí)一定會(huì)看到 b。兩重保障疊加答案不可能漏只是需要確保 check 的時(shí)候用嚴(yán)格的小于當(dāng)前最優(yōu)來(lái)判斷。這不是玄學(xué)是幾何性質(zhì)給出的硬保證。5. 復(fù)雜度與正確性分析5.1 遞推公式與 O(n log n)分治最近點(diǎn)對(duì)的時(shí)間復(fù)雜度需要認(rèn)真算一下。設(shè) T(n) 是處理 n 個(gè)點(diǎn)的時(shí)間遞歸時(shí)切成兩個(gè)規(guī)模為 n/2 的子問(wèn)題所以有 2T(n/2)。合并部分構(gòu)造 strip 需要遍歷 n 個(gè)點(diǎn)判斷是否在區(qū)域內(nèi)一次線性掃描O(n)。strip 內(nèi)按 y 排序時(shí)如果每一層都重新排序排序是 O(m log m)其中 m 是 strip 內(nèi)點(diǎn)數(shù)最壞情況下 m 接近 n合并就是 O(n log n)。于是遞推公式有兩種情況如果合并前對(duì) strip 重新排序T(n) 2T(n/2) O(n log n)解出來(lái) T(n) O(n log2 n)。如果做預(yù)排序優(yōu)化遞歸過(guò)程中始終保持 y 序列有序合并時(shí)直接線性歸并T(n) 2T(n/2) O(n)解出來(lái) T(n) O(n log n)。實(shí)際工程里我大多數(shù)時(shí)候用第一種簡(jiǎn)化實(shí)現(xiàn)因?yàn)閿?shù)據(jù)量在幾萬(wàn)以內(nèi)兩者差距不大。但如果是競(jìng)賽題或超大數(shù)據(jù)量必須用預(yù)排序優(yōu)化。預(yù)排序的做法是所有點(diǎn)一開(kāi)始按 x 排序進(jìn)入遞歸同時(shí)在主函數(shù)里維護(hù)一個(gè)按 y 排序的全局序列遞歸時(shí)把序列按 x 中位數(shù)分成兩份合并階段線性地把兩個(gè)有序 y 序列 merge 成一個(gè)。這樣每一層都是 O(n)總復(fù)雜度穩(wěn)定 O(n log n)。5.2 正確性論證的三個(gè)關(guān)鍵點(diǎn)分治算法能保證正確性靠的是三個(gè)環(huán)環(huán)相扣的結(jié)論。第一最優(yōu)解只有三種可能位置全在左半、全在右半、跨分割線。遞歸處理前兩種合并處理第三種覆蓋了所有情況。第二跨線最優(yōu)解的兩個(gè)點(diǎn)必然都在 strip 內(nèi)。這點(diǎn)前面已經(jīng)證明過(guò)水平距離小于等于兩點(diǎn)實(shí)際距離實(shí)際距離小于 d 就意味著水平距離小于 d。第三strip 內(nèi)按 y 排序后每個(gè)點(diǎn)只需要檢查后面有限個(gè)點(diǎn)。因?yàn)樵谝粋€(gè)高為 d 的窗口內(nèi)點(diǎn)的數(shù)量有常數(shù)上界。只要窗口內(nèi)的候選點(diǎn)沒(méi)有被漏掉檢查就不會(huì)錯(cuò)。這三個(gè)結(jié)論放在一起算法在邏輯上就是完備的。你可以用隨機(jī)數(shù)據(jù)反復(fù)驗(yàn)證我實(shí)測(cè)過(guò)大量隨機(jī)點(diǎn)集和暴力法對(duì)拍結(jié)果完全一致。5.3 排序優(yōu)化的細(xì)節(jié)為什么預(yù)處理后合并可以做到線性經(jīng)常有人問(wèn)既然 strip 要按 y 排序能不能每層直接 sort可以但不優(yōu)雅。每層 sort 會(huì)讓復(fù)雜度多一個(gè) log。預(yù)排序的核心思路是用空間換時(shí)間。一開(kāi)始就把點(diǎn)按 y 坐標(biāo)排好序然后在遞歸過(guò)程中保持這個(gè)順序不被打亂。具體實(shí)現(xiàn)是每層遞歸拿到的是已經(jīng)按 x 分好的左右兩個(gè)子數(shù)組以及一個(gè)按 y 排好序的全局?jǐn)?shù)組。按 y 排序的數(shù)組里逐個(gè)判斷點(diǎn)屬于左半還是右半分別放進(jìn)兩個(gè)臨時(shí)數(shù)組合并階段再把兩個(gè)臨時(shí)數(shù)組歸并回 y 有序數(shù)組。這樣每個(gè)點(diǎn)只在每一層被常數(shù)次掃描總時(shí)間 O(n log n)。這個(gè)優(yōu)化對(duì)理解很重要。我在一開(kāi)始學(xué)的時(shí)候只滿足于能算出正確答案沒(méi)想過(guò)排序帶來(lái)的額外 log后來(lái)做大規(guī)模數(shù)據(jù)處理時(shí)才意識(shí)到這個(gè)差異。如果你的數(shù)據(jù)量超過(guò)幾十萬(wàn)每層 sort 的 O(n log2 n) 會(huì)明顯拖慢速度預(yù)排序幾乎是必須的。6. 工程實(shí)現(xiàn)與踩坑筆記6.1 一份可以直接跑的 Python 參考實(shí)現(xiàn)下面是我實(shí)際常用的分支限界風(fēng)格寫(xiě)法加了不少注釋。我用平方距離比較來(lái)避免開(kāi)根號(hào)的浮點(diǎn)誤差最后一步再開(kāi)根。import math def sqdist(p1, p2): dx p1[0] - p2[0] dy p1[1] - p2[1] return dx * dx dy * dy def closest_pair(points): pts sorted(points) # 按 x 排序相同 x 按 y n len(pts) if n 2: return float(inf), None, None return _solve(pts, 0, n - 1) def _solve(pts, l, r): if l r: return float(inf), None, None if l 1 r: return sqdist(pts[l], pts[r]), pts[l], pts[r] mid (l r) // 2 mid_x pts[mid][0] dl, al, bl _solve(pts, l, mid) dr, ar, br _solve(pts, mid 1, r) if dl dr: best, pa, pb dl, al, bl else: best, pa, pb dr, ar, br # 收集 strip 內(nèi)的候選點(diǎn) strip [] for i in range(l, r 1): if abs(pts[i][0] - mid_x) best: strip.append(pts[i]) # 按 y 排序 strip.sort(keylambda p: p[1]) # 滑動(dòng)窗口檢查 m len(strip) for i in range(m): for j in range(i 1, m): if strip[j][1] - strip[i][1] best: break d sqdist(strip[i], strip[j]) if d best: best, pa, pb d, strip[i], strip[j] return best, pa, pb調(diào)用示例points [(1,30), (2,28), (3,31), (5,3), (6,4), (20,15), (21,13), (22,16)] d2, a, b closest_pair(points) print(a, b, math.sqrt(d2))輸出結(jié)果是(5, 3)(6, 4)1.4142135623730951和前面手工推演完全一致。6.2 邊界條件與遞歸出口遞歸出口是三件容易出問(wèn)題的事。首先是單點(diǎn)情況區(qū)間里只有一個(gè)點(diǎn)沒(méi)有點(diǎn)對(duì)直接返回?zé)o窮大。我的代碼里用l r處理。其次是兩個(gè)點(diǎn)的情況直接計(jì)算距離返回避免繼續(xù)劃分。不寫(xiě)這個(gè)出口的話兩個(gè)點(diǎn)會(huì)被切成一個(gè)點(diǎn)加空區(qū)間空區(qū)間返回?zé)o窮大合并時(shí) strip 掃一遍也能得到正確結(jié)果但多一層無(wú)意義遞歸代碼也不清晰。第三是重復(fù)點(diǎn)。如果兩個(gè)點(diǎn)坐標(biāo)完全相同理論上它們的距離是 0是全局最優(yōu)算法會(huì)立刻發(fā)現(xiàn)。但要注意 strip 收集條件里的浮點(diǎn)比較。如果 best 已經(jīng)變成 0那 strip 里只有 x 完全相同的點(diǎn)滑動(dòng)窗口依然能處理。最穩(wěn)妥的做法還是在主函數(shù)一開(kāi)始先做一次去重檢測(cè)存在重復(fù)點(diǎn)直接返回 0。6.3 浮點(diǎn)精度與比較策略距離比較有一條小經(jīng)驗(yàn)不要在遞歸內(nèi)部用math.sqrt。開(kāi)根號(hào)是浮點(diǎn)運(yùn)算不但慢而且累積誤差會(huì)讓比較變得不干凈。我全程用平方距離最后在返回時(shí)才開(kāi)一次根。這樣既快又準(zhǔn)。另一個(gè)容易踩的坑是 strip 邊界的等號(hào)判斷。我建議用而不是。因?yàn)槿绻麅蓚€(gè)點(diǎn)的距離恰好等于當(dāng)前最優(yōu)值用把它們排除在 strip 外也不影響更新答案反正不會(huì)變得更優(yōu)但用可以避免一些邊界爭(zhēng)議實(shí)現(xiàn)上更安全。不過(guò)要注意如果整個(gè)算法允許返回等距的多個(gè)解那必須用并且在比較時(shí)用更新。通常題目只要求任意一個(gè)最近點(diǎn)對(duì)所以代碼里不必過(guò)度糾結(jié)。6.4 常見(jiàn)問(wèn)題速查表現(xiàn)象可能原因解決方法答案偏大合并時(shí)漏了 strip 區(qū)域內(nèi)的候選點(diǎn)檢查 strip 收集條件確認(rèn)用的是當(dāng)前最優(yōu)值 d答案偏大滑動(dòng)窗口內(nèi)提前 break確認(rèn) break 條件用的是 y 差值大于等于 d而不是大于復(fù)雜度退化到 O(n2)strip 內(nèi)所有點(diǎn)兩兩都比較必須按 y 排序并用 y 差值剪枝重復(fù)點(diǎn)返回異常沒(méi)有處理坐標(biāo)完全相同的點(diǎn)主函數(shù)開(kāi)頭特判存在重復(fù)點(diǎn)直接返回 0浮點(diǎn)誤差導(dǎo)致邊界判斷失誤遞歸內(nèi)部用開(kāi)根后的距離做比較全程用平方距離比較最后再開(kāi)根輸出點(diǎn)對(duì)與暴力法不一致多個(gè)最優(yōu)解選擇了不同的一對(duì)只要距離相等任何一對(duì)都算正確不用糾結(jié)7. 寫(xiě)在最后畫(huà)圖理解與個(gè)人體會(huì)我個(gè)人在實(shí)際學(xué)習(xí)中的體會(huì)是像最近點(diǎn)對(duì)這種幾何味很重的算法光看文字推導(dǎo)效率很低畫(huà)圖幾乎是必須的。把點(diǎn)標(biāo)在坐標(biāo)系上畫(huà)出分割線、畫(huà)出 strip、畫(huà)出按 y 排序后的滑動(dòng)窗口整個(gè)算法的每一步都有了直觀載體。我當(dāng)年就是親手在紙上把 8 個(gè)點(diǎn)的例子推演了一遍才徹底搞懂為什么合并階段只需要檢查常數(shù)個(gè)點(diǎn)。如果你也在學(xué)這個(gè)算法建議拿筆照著文中的 8 個(gè)點(diǎn)自己畫(huà)一遍遞歸樹(shù)再畫(huà)一遍 strip 區(qū)域。畫(huà)到合并那一步看到 (5,3) 和 (6,4) 這兩個(gè)跨線的點(diǎn)在 strip 里相遇時(shí)那種原來(lái)如此的感覺(jué)是看多少篇文章都換不來(lái)的。最后再分享一個(gè)小技巧寫(xiě)完分治實(shí)現(xiàn)后一定寫(xiě)一個(gè)暴力解法做對(duì)拍隨機(jī)生成幾千組點(diǎn)集逐一比對(duì)結(jié)果。這個(gè)習(xí)慣幫我排查掉了大量邊界 bug也是我寫(xiě)任何算法題都會(huì)做的第一件事。算法寫(xiě)出來(lái)是給人看的但正確性最終要靠數(shù)據(jù)說(shuō)話。