wordpress安装memcached百度seo排名推广

在数组nums中找到p个数对，使差值绝对值的和最小。

思路：

最小差值应该是数值相近的一对数之间产生，让数值相近的数字尽量靠在一起方便计算，所以需要排序。
这里不去直接考虑一对对的数字，而是直接考虑差值的取值。

用binary search搜索一个差值。
左边界是0，右边界就是nums中的最大值 - 最小值（nums排序后最右边数字 - 最左边数字）。

确定mid = 差值，那么一对数字的差的绝对值如果 <= 这个差值，就说明满足，
遍历数组nums, 计算满足 <= 差值的数字有多少对，记为cnt对，
如果cnt >= p, 说明差值在mid内的数字对能达到p个，可以进一步缩小差值，right= mid.
反之需要left = mid+1.

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可以是0if(nums[i+1] - nums[i] <= mid) {cnt ++;i ++;  //加上for里面的i++,相当于i向右移动2位}}return cnt >= p;}
}