广西网络公司有几家北京seo全网营销
2023-03-29每日一题
一、题目编号
二、题目链接
点击跳转到题目位置
三、题目描述
给你一个正整数数组 price ,其中 price[i] 表示第 i 类糖果的价格,另给你一个正整数 k 。
商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。
返回礼盒的 最大 甜蜜度。
提示:
- 1 <= price.length <= 105
- 1 <= price[i] <= 109
- 2 <= k <= price.length
四、解题代码
class Solution {bool judge(int degree, vector<int> &price , int k, int n){int num = 1;int index = price[0];for(int i = 1; i < n; ++i){if(price[i] - index >= degree){index = price[i];++num;}}if(num >= k){return true;}return false;}public:int maximumTastiness(vector<int>& price, int k) {sort(price.begin(), price.end());int n = price.size();int left = 0;int right = price[n - 1] - price[0];int ans = -1;while(left <= right){int mid = ((right - left) >> 1) + left;if(judge(mid, price, k, n) == true){ans = mid;left = mid+1;} else{right = mid-1;}}return ans;}
};
五、解题思路
(1) 这道题目采用的是二分答案+贪心的方式来解决本道题目。
(2) 首先将价格从低到高来进行排序,那么最小的甜蜜度肯定为0,最大的甜蜜度肯定为price[n-1] - price[0]。那么我们就可以用二分答案的方式,在这个甜蜜度区间内进行查找,直到查找到答案。
(3) 那么我们怎么判断二分查找的答案是正确的呢。假设我们判断甜蜜度degree的答案是正确,那就是遍历一个有序数组,找到k个满足间隔大于等于degree的数。这个问题显然是熟悉的贪心思路(样板为活动安排问题)。
(4) 最后返回二分搜索出来的答案即可。