HRT 电面面经

匿名者 发表于 2021-11-11 00:51
最后在面试官的提示下可以从O(nlogn)优化到O(n)。方法是每次partition的时候都partition长的那个dimensio ...

老哥能详细说说么，我没太理解（我比较菜。。。
2d的咋能做到linear呀？多谢！

假设一开始是个正方形，每次都对长的边做binary search，每两次操作会使matrix size变为原来的1/4。全加起来是converge to linear complexity