題目連結:
題目意譯:
你被給定一正整數陣列 price 以及一整數 k,其中 price[i] 代表著第 i 顆糖果的價格。
有間店鋪販賣著裝有 k 個相異糖果的籃子。一個糖果籃的美味程度為籃子中任兩顆糖果的價格絕對差值之最小值。
回傳一個糖果籃的最大美味程度。
限制:
2 ≦ k ≦ price.length ≦ 10 ^ 5
1 ≦ price[i] ≦ 10 ^ 9
範例測資:
範例 1:
輸入: price = [13,5,1,8,21,2], k = 3
輸出: 8
解釋: 選擇價格為 [13,5,21] 的糖果。
該糖果籃子的美味程度為:min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8, 16) = 8。
可以證明 8 是最大可被達成的美味程度。
範例 2:
輸入: price = [1,3,1], k = 2
輸出: 2
解釋: 選擇價格為 [1,3] 的糖果。
該糖果籃子的美味程度為:min(|1 - 3|) = min(2) = 2。
可以證明 2 是最大可被達成的美味程度。
範例 3:
輸入: price = [7,7,7,7], k = 2
輸出: 0
解釋: 選擇任意兩顆相異糖果我們將得到美味程度 0。
解題思維:
先將 price 中的數字按照數值大小由小到大排。
接著對答案本身進行二分搜尋法(Binary Search)即可,如
這題。
那要怎麼檢查我們猜的美味程度 M 太小或太大?很簡單,取(排序後)第一顆糖果然後重複:
令當前最後一顆取的糖果價格為 C,則下一顆只能取價格大於等於 C + M 的糖果
之條件來掃過整個陣列 price 即可。
過程中取的糖果數必將是美味程度固定為 M 的情況下,能取的最大糖果數(證明部分在此省略,基本上就是反證法)。
因此如果此時的糖果數 < k,則代表我們猜得太大了,必須猜小一點;反之,則有「可能」可以猜大一點。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。