在數(shù)組nums中找到p個數(shù)對，使差值絕對值的和最小。
思路：
最小差值應該是數(shù)值相近的一對數(shù)之間產(chǎn)生，讓數(shù)值相近的數(shù)字盡量靠在一起方便計算，所以需要排序。
這里不去直接考慮一對對的數(shù)字，而是直接考慮差值的取值。
用binary search搜索一個差值。
左邊界是0，右邊界就是nums中的最大值 - 最小值（nums排序后最右邊數(shù)字 - 最左邊數(shù)字）。文章來源：http://www.zghlxwxcb.cn/news/detail-635977.html
確定mid = 差值，那么一對數(shù)字的差的絕對值如果 <= 這個差值，就說明滿足，
遍歷數(shù)組nums, 計算滿足 <= 差值的數(shù)字有多少對，記為cnt對，
如果cnt >= p, 說明差值在mid內(nèi)的數(shù)字對能達到p個，可以進一步縮小差值，right= mid.
反之需要left = mid+1.文章來源地址http://www.zghlxwxcb.cn/news/detail-635977.html
class Solution {
int n = 0;
public int minimizeMax(int[] nums, int p) {
n = nums.length;
Arrays.sort(nums);
int left = 0;
int right = nums[n-1] - nums[0];
while(left < right) {
int mid = left + (right - left) / 2;
if(canMakePairs(mid, nums, p)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
boolean canMakePairs(int mid, int[] nums, int p) {
int cnt = 0;
for(int i = 0; i < n-1 && cnt < p;i++){ //在這里限制cnt<p,因為p可以是0
if(nums[i+1] - nums[i] <= mid) {
cnt ++;
i ++; //加上for里面的i++,相當于i向右移動2位
}
}
return cnt >= p;
}
}
到了這里，關于leetcode 2616. 最小化數(shù)對的最大差值的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
