额敏网站建设,付费wordpress主题,免费网站开发模板,中国最大型网站礼盒的最大甜蜜度
题目描述
给你一个正整数数组 price #xff0c;其中 price[i] 表示第 i 类糖果的价格#xff0c;另给你一个正整数 k 。
商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。
返回礼盒的 最大 甜蜜度。…礼盒的最大甜蜜度
题目描述
给你一个正整数数组 price 其中 price[i] 表示第 i 类糖果的价格另给你一个正整数 k 。
商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。
返回礼盒的 最大 甜蜜度。
样例
样例输入 price [13,5,1,8,21,2], k 3 price [1,3,1], k 2 price [7,7,7,7], k 2 样例输出 8 2 0 提示
1price.length1051 price.length 10^51price.length1051price[i]1091 price[i] 10^91price[i]1092kprice.length2 k price.length2kprice.length
思路
答案具有单调性且n的范围为10510^5105, 只能使用O(nlogn)O(nlogn)O(nlogn)可直接使用二分
代码实现
class Solution {int[] price;int k;public int maximumTastiness(int[] price, int k) {Arrays.sort(price);this.price price;this.k k;int l 0;int r price[price.length-1];while(l r){int mid (r l) / 2;if(!check(mid)) r mid - 1;else l mid 1;}return r;}private boolean check(int x){int ans 1;int max price[0];for(int i 1; i price.length; i){if(price[i] max x){max price[i];ans;}}return ans k;}
}
