→ moonoftree: 沒人在乎 09/29 23:34
→ pandix: 樹樹快教高中生刷leetcode== 09/29 23:46
→ Rushia: 太難了 排序問題一律HEAP硬幹 09/29 23:46
→ moonoftree: 別傻了 = = 他們連 kg 跟 g 都搞不清楚 09/30 00:02
※ 引述《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我超
--
沒人在乎
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.233.144 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1664465610.A.B72.html