https://i.imgur.com/rthlGB3.jpg
學校程式題有出到這題 一直TLE
稍微研究了一下 發現林立宇的code好像有錯
大概以下幾點，如果有人知道我哪邊理解錯 請跟我說
-
1. 林的版本跟楓葉本不一樣 不知道是哪本原文書的？
2. 他的遞迴要 merge 的時候應該是只要找該遞迴區間（不能K 從頭掃到尾）
3. 但是根據 2 你原陣列跟 K 的區間的點不會一樣
（意思就是 可能你index 6～10 的點 在K跟原陣列不會是同一批點）
4. 所以不能用到那個鴿籠原理（只找7個點） 因為你沒辦法線性時間內找到同時符合|x-m|<=d 然後又可以根據他們y座標排好的順序取點（因為這些 |x-m|<=d 的點在K的位置你不知道）
5. 所以林的版本複雜度應該是n^2 不然程式會錯

merge 應該是 k 從頭掃到尾

我這幾天研究完了～ 實際上不能從頭掃到尾 這樣一定是n^2林立宇這邊講的沒有很清楚 詳細可以參考網路上其他資源，正確做法是維護兩個陣列，一個是對x sort (x座標相同則再對y 排，否則會無法分成n/2） 一個是對y sort 然後兩個陣列都要切半如果按照林立宇的版本，一直都是對你presort 的 K 從頭掃到尾的話 複雜度會是n^2 不信的可以寫程式跑跑看就知道了

離題，想請問有資工考科的賴群嗎？

對 x sort 不是必須的，只要找到 median 就可以切了兩個陣列都要切半是沒錯 這樣才能減少搜尋範圍

ADA崩潰中