※ 引述《pandix (面包屌)》之铭言：
: ※ 引述《Rushia (みけねこ的鼻屎)》之铭言：
: : 658. Find K Closest Elements
: : 说明：
: : 给定一个排序好的阵列arr、一个数字k和一个数字x，我们需返回一个大小为k的列表，
: : 其中的数字要是最接近x的数字，若数字一样接近则数字小的优先，返回的列表必须也是
: : 排序好的。
: : Example 1:
: : Input: arr = [1,2,3,4,5], k = 4, x = 3
: : Output: [1,2,3,4]
: 思路:
: 1.看到题目给 sorted array 直觉就是 binary search
: 可以O(log(n))搜到 x 能插入的位置 也就是 a[i] <= x <= a[i+1]
: python 的 bisect.left 可以插到 a[i] < x <= a[i+1]
: 2.之后就比较 a[i] 和 a[i+1] 哪个离 x 比较近 然后后面就老招了
: 维护左界右界 左边离 x 比较近就往左推 反之往右推
: 3.不停比较直到右界-左界>k
: 时间复杂度O(log(n)+k)
看到了lee的解法 果然还是lee厉害
上一篇的解法虽然有用 binary search 压复杂度
但要找到实际的左界右界还是会被 k bound住 可以想像 [1,1,1,1,2], x=2, k=4
当k很大的时候要往左移很多次
那有没有办法一次搜到位? 有
原本在 binary search 的时候 往左往右判断的基准也就是 key 是 a[i]<x
现在把这个 key 换成 x-a[i] > a[i+k]-x
意思是假设我们的目标阵列在 a[i]~a[i+k] = a[i:i+k+1] 当中
这里要注意他其实有k+1个元素在里面 所以实际目标候选是 a[i:i+k] 跟 a[i+1:i+k+1]
怎么知道哪个是更好的答案 就是比较 x-a[i] > a[i+k]-x
如果True则代表 a[i+1:i+k+1] = a[i+1:i+k] + a[i+k] 更好 因此i往右半搜
反之则代表 a[i:i+k] = a[i+1:i+k] + a[i] 更好 因此i往左半搜
这样就能O(log(n-k)) 一次搜到位
log(n-k) 是因为 i 的最大可能是 n-k
感觉解释的不是很好 建议看一下lee那篇 网址太长就不贴了
虽然复杂度因为最后要 slice list 还是会被 k bound 住
不过如果只要你传 index 这就是更好的解法
lee我超