距离目标值第Cth近的

@14417335 at一下版主看有没有思路。看上面的回复。

mhsasd 发表于 2019-3-31 23:18
@14417335 at一下版主看有没有思路。看上面的回复。

没有特别明白你10垅的问题。找到了长度为C的子数组的开始，头尾哪个更小就返回哪个。如果面试官还有特别的要求，比如tie的时候返回index更小的，照做就是。

14417335 发表于 2019-3-31 23:33
没有特别明白你10垅的问题。找到了长度为C的子数组的开始，头尾哪个更小就返回哪个。如果面试官还有特别 ...

比方说在【1，2，3】找跟2第三个最近的元素。
你的意思是说因为1和3的离2一样近，这时候返回最小的所以是1.

但是，你这样iterative的想一下，第一个最小的是2对吧。这时候要找第二个。那第二个最小的1还是3呢，因为是tie所以应该是1. 然后第三个我们要的就只有3了。

不知道说的清不清楚。

mhsasd 发表于 2019-3-31 23:39
比方说在【1，2，3】找跟2第三个最近的元素。
你的意思是说因为1和3的离2一样近，这时候返回最小的所以 ...

不知道为什么要iterative。target第Cth近的一定是头或者尾。哪个和target的差距越大就是那个。
如果数组是
- 1 2 4 找跟2第三个最近的元素, BS找到了[0]，那么一定在1 和 4 里。发现4-2>2-1所以应该是4。
- 1 2 3 找跟2第三个最近的元素, BS找到了[0]，那么一定在1 和 3 里。发现3-2==2-1所以再根据面试官的要求返回那个。

14417335 发表于 2019-4-1 00:15
不知道为什么要iterative。target第Cth近的一定是头或者尾。哪个和target的差距越大就是那个。
如果数组 ...

好像确实不用iterative的找。应该是我想多了。哈哈 谢谢楼主