leetcode 2616. 最小化数对的最大差值-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode 2616. 最小化数对的最大差值。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

leetcode 2616. 最小化数对的最大差值,leetcode,leetcode,算法

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

思路：

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

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

确定mid = 差值，那么一对数字的差的绝对值如果 <= 这个差值，就说明满足，
遍历数组nums, 计算满足 <= 差值的数字有多少对，记为cnt对，
如果cnt >= p, 说明差值在mid内的数字对能达到p个，可以进一步缩小差值，right= mid.
反之需要left = mid+1.文章来源地址https://www.toymoban.com/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;
    }
}