距离目标值第Cth近的

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

关于双倍积分奖励算法题和系统设计题讨论的决定：

我们：
1. 希望能看到干货讨论；
2. 希望能看到好的代码（web端高级发帖模式下，@ 朋友右边的<> 可以选择多种代码）

版主 @14417335 负责审核加分，也请大家给好的回复加分 + 顶。
大家给30，我会跟进奖励30，double之；
大家给100，我也会跟进奖励100，double之。

很理解大家写代码、调试、写思路分析，很花时间。对于特别好的回复，还会有额外加分。

欢迎大家拿出好的题目讨论，选中了我会全站置顶。哪位同学起了好的题目/帖子，激发了干货讨论，也会获得一定的积分奖励。

欢迎大家踊跃参与。看到好的回复，也请大家顶一下，作为对别人积极参与讨论、热心分享的认可和鼓励。
其他可以获得双倍积分的题目：

在刷题版里选择高频题标签，链接:
https://www.1point3acres.com/bbs/forum.php?mod=forumdisplay&fid=84&filter=typeid&typeid=1019

大家看到LC没有的高频题，也请贴到刷题版里，又有大米又有赞。对于学弟学妹们也是功劳一件。举手之劳。谢谢大家的参与。

kaipeng21 发表于 2019-3-26 09:25
复杂度logN，看利口最高票lee215的解，只是原题要求要返回全部k个数的值，所以原题会是O(logN+K), 这题只 ...

跟lee大神的解法可以找到一个size 为k的一个List， 满足里面就是要的就是前k个元素。但是如果只要第k个，那是应该返回第一个还是最后一个呢？

比方说【1，2，3】x=2 找第3个。如果always use min break tie是针对最终结果的，那很简单，判断首尾距离差就可以了；但是如果针对每一步判断的话，1st 2, 2nd 1(1, 3选择了1), 3nd 3.应该是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所以再根据面试官的要求返回那个。

这题其实就是刷题网瘤舞笆，最后高矮两个点找远的吧

补充内容 (2019-3-25 12:27):
更正一下，应该是左边就好了

补充内容 (2019-3-27 05:23):
再更正，我想错了，确实要两端找远的

kaipeng21 发表于 2019-3-25 11:45
这题其实就是刷题网瘤舞笆，最后高矮两个点找远的吧

补充内容 (2019-3-25 12:27):

是的，只需要取第一个数就是答案了

kaipeng21 发表于 2019-3-25 11:45
这题其实就是刷题网瘤舞笆，最后高矮两个点找远的吧

补充内容 (2019-3-25 12:27):

复杂度能符合面试官的要求么？

14417335 发表于 2019/03/26 09:13:19


复杂度能符合面试官的要求么？

复杂度logN，看利口最高票lee215的解，只是原题要求要返回全部k个数的值，所以原题会是O(logN+K), 这题只要一个就O(logN)

kaipeng21 发表于 2019-3-25 11:45
这题其实就是刷题网瘤舞笆，最后高矮两个点找远的吧

补充内容 (2019-3-25 12:27):

为什么只取左边啊，如果c=4用上面那个例子，返回的不是应该是20吗

zdj0712 发表于 2019/03/27 04:27:59


为什么只取左边啊，如果c=4用上面那个例子，返回的不是应该是20吗

是我想错了，最后binary search找到的是A[m]和A[m+C], 确认A[m+C]到K的距离一定>=A[m]到K的距离，但不保证A[m+C-1]到K比A[m]到K近

kaipeng21 发表于 2019-3-26 09:25
复杂度logN，看利口最高票lee215的解，只是原题要求要返回全部k个数的值，所以原题会是O(logN+K), 这题只 ...

对，是log（N）

。。。。。字数