[問題] leetcode 658

[sean72 (.)]

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://www.ptt.cc/bbs/Python/M.1532735232.A.1F3.html
推 handsomeLin: loop完之後你的s e差是1 你的if是比窗口第一個跟窗口
→ handsomeLin: 外的第一個 所以最後選窗口要不要右移 就這樣
是的，我一開始寫的時候也是這麼想，
但有點想不通(感覺有點懂，但又不是完全懂)
為什麼 |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
推 handsomeLin: 因為你窗口大小固定是K
推 handsomeLin: 你是 大於的話選 窗外的 小於才選原本窗內的