神农架网站制作,网站推广策划书目录,wordpress默认登录地址修改,深圳最新政策在数组nums中找到p个数对#xff0c;使差值绝对值的和最小。
思路#xff1a;
最小差值应该是数值相近的一对数之间产生#xff0c;让数值相近的数字尽量靠在一起方便计算#xff0c;所以需要排序。 这里不去直接考虑一对对的数字#xff0c;而是直接考虑差值的取值。
…
在数组nums中找到p个数对使差值绝对值的和最小。
思路
最小差值应该是数值相近的一对数之间产生让数值相近的数字尽量靠在一起方便计算所以需要排序。 这里不去直接考虑一对对的数字而是直接考虑差值的取值。
用binary search搜索一个差值。 左边界是0右边界就是nums中的最大值 - 最小值nums排序后最右边数字 - 最左边数字。
确定mid 差值那么一对数字的差的绝对值如果 这个差值就说明满足 遍历数组nums, 计算满足 差值的数字有多少对记为cnt对 如果cnt p, 说明差值在mid内的数字对能达到p个可以进一步缩小差值right mid. 反之需要left mid1.
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){ //在这里限制cntp,因为p可以是0if(nums[i1] - nums[i] mid) {cnt ;i ; //加上for里面的i,相当于i向右移动2位}}return cnt p;}
}
