作者sean72 (.)
看板Python
标题[问题] leetcode 658
时间Sat Jul 28 07:47:08 2018
658. Find K Closest Elements
https://leetcode.com/problems/find-k-closest-elements/description/
https://paste.ubuntu.com/p/TCH82fyZ4j/
整段代码是可以通过的
但是有很多幸运成份，自己也想不通，
目标：找到一个窗口size k ，此窗口里面元素尽量靠近target x
若是距离x一样，窗口尽量靠左
假设窗口左端点为s 和 e
二分法移动选取窗口
# s...m.......x...m+k-1...e
# 如果x比左端点远，则s右移，使得窗口右移
# 反之，e左移，使得窗口左移
# 问题：如果x距离左右端点距离相同 x - arr[m] == arr[m+k-1] - x
# 应该左移还是右移?
# 我误打误撞选了左移
(自问自答:因为题目说，若是相同，则尽量取靠左)
# 离开while loop後，考虑答案为 arr[s : s+k] or arr[e : e+k]
# 为什麽下面这样是对的？
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 8.41.187.50
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Python/M.1532735232.A.1F3.html
1F：推 handsomeLin: loop完之後你的s e差是1 你的if是比窗口第一个跟窗口 07/28 08:12
2F：→ handsomeLin: 外的第一个 所以最後选窗口要不要右移 就这样 07/28 08:12
是的，我一开始写的时候也是这麽想，
但有点想不通(感觉有点懂，但又不是完全懂)
为什麽 |x-arr[s]| 距离 小於 |arr[s+k]-x|
第一个窗口 距离 小於 窗口外第一个
可以推得 ==> 我应该要选 arr[e : e+k] ?
(因为x更靠近arr[s+k] 所以k个点应该要更靠右?)
※ 编辑: sean72 (172.89.32.145), 07/28/2018 14:11:47
※ 编辑: sean72 (172.89.32.145), 07/28/2018 14:53:38
3F：推 handsomeLin: 因为你窗口大小固定是K 07/29 09:01
4F：推 handsomeLin: 你是 大於的话选 窗外的 小於才选原本窗内的 07/29 09:03