太和县住房和城乡建设局网站,安钢贴吧论坛,手机医疗网站建设,关键词网站给你一个下标从 0 开始的整数数组 nums 和一个整数 p 。请你从 nums 中找到 p 个下标对#xff0c;每个下标对对应数值取差值#xff0c;你需要使得这 p 个差值的 最大值 最小。同时#xff0c;你需要确保每个下标在这 p 个下标对中最多出现一次。
对于一个下标对 i 和 j 每个下标对对应数值取差值你需要使得这 p 个差值的 最大值 最小。同时你需要确保每个下标在这 p 个下标对中最多出现一次。
对于一个下标对 i 和 j 这一对的差值为 |nums[i] - nums[j]| 其中 |x| 表示 x 的 绝对值 。
请你返回 p 个下标对对应数值 最大差值 的 最小值 。
示例 1
输入nums [10,1,2,7,1,3], p 2
输出1
解释第一个下标对选择 1 和 4 第二个下标对选择 2 和 5 。
最大差值为 max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) max(0, 1) 1 。所以我们返回 1 。示例 2
输入nums [4,2,1,2], p 1
输出0
解释选择下标 1 和 3 构成下标对。差值为 |2 - 2| 0 这是最大差值的最小值。
提示
1 nums.length 10^50 nums[i] 10^90 p (nums.length)/2
分析二分答案左端点为 0右端点为数组元素的最大值检查能否找到 p 个差值小于等于 mx 的数对。先对数组进行排序之后相邻元素的差如果小于 mx就计算一次差值循环下标右移 2 位否则循环下标右移 1 位。
检查满足差值小于等于 mx 的数对个数。贪心进行选择从左到右遍历时只要 nums[i] 与 nums[i1] 构成的数对满足条件就立刻选取。假设不选 nums[i]从剩下的数中能够选出的对数一定不会超过选 nums[i] 时的对数所以贪心策略是正确的。
int cmp(const void *a,const void *b)
{int *aa(int*)a;int *bb(int*)b;return (*aa)-(*bb);
}int minimizeMax(int* nums, int numsSize, int p) {if(!p)return 0;qsort(nums,numsSize,sizeof(int),cmp);// for(int i0;inumsSize;i)// printf(%d ,nums[i]);int ans0,l0,rnums[numsSize-1],mid;while(lr){// printf(l%d r%d\n,l,r);int mid(lr)/2,cnt0;for(int i1;inumsSize;){int sumnums[i]-nums[i-1];if(summid)cnt,i2;else i;}if(cntp)ansmid,rmid-1;else lmid1;// printf(l%d r%d cnt%d p%d mid%d ans%d\n,l,r,cnt,p,mid,ans);}return ans;
}
