最小化数对的最大差值

题目

6359. 最小化数对的最大差值

---

给你一个下标从 0 开始的整数数组 nums 和一个整数 p 。请你从 nums 中找到 p 个下标对，每个下标对对应数值取差值，你需要使得这 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^5
• 0 <= nums[i] <= 10^9
• 0 <= p <= (nums.length)/2

题解

方法一：

思路

在排序后，只有选相邻的两个数才能尽可能的让差值小。

假设最大差值的最小值为x，那么我们从左至右贪心的统计差值小于等于x的点对数cnt，如果大于p，说明x还可以增大。
当我们找到由小到大找到第一个使得cnt等于p的x便是答案。这可以通过二分查找得到快速找到。

代码

class Solution {
public:
    using ll = long long;
    int minimizeMax(vector<int>& nums, int p) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        ll l=0, r=1e9+7;
        while (l<r) {
            ll m = l+r>>1;
            int i = 0, cnt = 0;
            while (i+1<n) {
                if (nums[i+1]-nums[i]<=m) cnt++,i++;
                i++;
            }
            if (cnt>=p) {
                r = m;
            } else {
                l = m+1;
            }
        }
        return r;
    }
};