禮盒的最大甜蜜度【LC2517】
You are given an array of positive integers
pricewhereprice[i]denotes the price of theithcandy and a positive integerk.The store sells baskets of
kdistinct candies. The tastiness of a candy basket is the smallest absolute difference of the prices of any two candies in the basket.Return the maximum tastiness of a candy basket.
最大化最小化類似題目
-
思路：使用二分查找的方式尋找最大甜蜜度
- 本題的單調(diào)性為：當(dāng)**最小甜蜜度【數(shù)組中任意兩個(gè)元素的差值的絕對(duì)值的最小值】**越大，糖果的可以選擇的種類越小【選取的數(shù)組中的元素個(gè)數(shù)】，因此可以通過(guò)二分查找法找到最終答案
- 將題意轉(zhuǎn)化為：當(dāng)選取的數(shù)量一定時(shí)，尋找最小甜蜜度的最大值 y y y，二分查找的下限為0，上限為數(shù)組中最大元素與最小元素的差值/（k-1）
-
實(shí)現(xiàn)
-
首先對(duì)
price數(shù)組進(jìn)行升序排序 -
然后進(jìn)行二分查找，當(dāng)二分查找最小甜蜜度 y y y時(shí)，需要判斷能否取出 k k k種糖果，如果能取出 k k k種糖果，那么我們可以增大差值，已獲得更大的最小甜蜜度；如果不能取出 k k k中糖果，那么減小差值
-
每次查找成功，記錄當(dāng)前的最小甜蜜度，最后一次的最小甜蜜度即為最大最小甜蜜度
-
如何判斷當(dāng)前的差值能夠取出多少種糖果？
模擬迭代，第一種糖果取 p r i c e [ 0 ] price[0] price[0]，第一種糖果取 p r i c e [ 0 ] + y price[0]+y price[0]+y的 p r i c e [ i ] price[i] price[i]處……文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-467361.html
-
-
代碼文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-467361.html
class Solution { public int maximumTastiness(int[] price, int k) { Arrays.sort(price); int n = price.length; int l = 0, r = price[n - 1] - price[0]; int ans = 0; while (l <= r){ int mid = (r + l) / 2; if (check(price, mid ,k)){ ans = mid; l = mid + 1; }else{ r = mid - 1; } } return ans; } public boolean check(int[] price, int m, int k){ int count = 1; int preIndex = 0; for (int i = 1; i < price.length; i++){ if (price[i] - price[preIndex] >= m ){ count++; preIndex = i; } } return count >= k; } }- 復(fù)雜度
- 時(shí)間復(fù)雜度： O ( n l o g ( n C ) ) O(nlog(nC)) O(nlog(nC))， n n n是數(shù)組的長(zhǎng)度，C是數(shù)組中的最大值與最小值的差值。排序需要的時(shí)間復(fù)雜度為 O ( n l o g n ) O(nlog n) O(nlogn)，二分查找的時(shí)間復(fù)雜度是 O ( l o g C ) O(logC) O(logC)，每次二分查找需要判斷是否符合條件的時(shí)間復(fù)雜度為 O ( n ) O(n) O(n)，因此總的時(shí)間復(fù)雜度為 O ( n l o g ( n c ) ) O(nlog(nc)) O(nlog(nc))
- 空間復(fù)雜度： O ( l o g n ) O(logn) O(logn)，排序所需要的?？臻g
- 復(fù)雜度
到了這里，關(guān)于【每日一題Day224】LC2517禮盒的最大甜蜜度 | 二分答案的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
