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

链接：2616.最小化数对的最大差值
难度：Medium
标签：贪心、数组、二分查找
简介：给你一个下标从 0 开始的整数数组 nums 和一个整数 p 。请你从 nums 中找到 p 个下标对，每个下标对对应数值取差值，你需要使得这 p 个差值的 最大值 最小。同时，你需要确保每个下标在这 p 个下标对中最多出现一次。对于一个下标对 i 和 j ，这一对的差值为 |nums[i] - nums[j]| ，其中 |x| 表示 x 的 绝对值 。请你返回 p 个下标对对应数值 最大差值 的 最小值 。

题解 1 - rust

• 编辑时间：2023-04-09
• 执行用时：24ms
• 内存消耗：3.3MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn minimize_max(mut nums: Vec<i32>, p: i32) -> i32 {
        nums.sort();
        let n = nums.len();
        let (mut l, mut r) = (0, *nums.iter().max().unwrap());
        let check = |target: i32| -> bool {
            let mut cnt = 0;
            let mut i = 0;
            while i < n && cnt < p {
                if i + 1 < n && nums[i + 1] - nums[i] <= target {
                    i += 1;
                    cnt += 1;
                }
                i += 1;
            }
            cnt >= p
        };
        while l < r {
            let m = (l + r) / 2;
            if check(m) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        l
    }
}

题解 2 - python

• 编辑时间：2023-04-09
• 执行用时：1140ms
• 内存消耗：29.6MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        nums.sort()
        n = len(nums)
  
        def check(target: int) -> bool:
            cnt = 0
            i = 0
            while i < n and cnt < p:
                if i + 1 < n and nums[i + 1] - nums[i] <= target:
                    i += 1
                    cnt += 1
                i += 1
            return cnt >= p
        l, r = 0, 1000000000+7
        while l < r:
            m = (l + r) // 2
            if check(m):
                r = m
            else:
                l = m+1
        return l

题解 3 - cpp

• 编辑时间：2023-04-09
• 执行用时：160ms
• 内存消耗：79.3MB
• 编程语言：cpp
• 解法介绍：最大最小，二分查找。

class Solution {
public:
    int minimizeMax(vector<int>& nums, int p) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        auto check = [&](int target) -> bool {
            int cnt = 0;
            for(int i = 0; i < n && cnt < p; i++){
                if (i + 1 < n && nums[i + 1] - nums[i] <= target) i++, cnt++;
            }
            return cnt >= p;
        };
        int l = 0, r = 1e9 + 7;
        while(l < r){
            int mid = (l + r) / 2;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};