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崩溃中