Medium

题目描述

给你一个下标从 0 开始的整数数组 nums 和一个整数 p。请你从 nums 中找到 p 对数字，使得这 p 对数字中 最大 的差值 最小。同时，你需要确保每个下标在这 p 对数字中最多出现 一次。

对于一对元素，下标为 i 和 j，这一对的差值为 |nums[i] - nums[j]|，其中 |x| 表示 x 的 绝对值。

返回 p 对数字中 最大差值 的 最小值。我们定义空集合的最大值为 0。

示例 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

解题思路

这是一道典型的二分搜索 + 贪心问题。

核心思路：

  1. 排序优化：首先对数组排序，这样相邻或接近的元素会靠在一起，有利于找到较小的差值
  2. 二分搜索答案：在可能的最大差值范围内进行二分搜索。最小值为0，最大值为排序后数组的最大值与最小值之差
  3. 贪心验证：对于每个候选答案，使用贪心策略验证是否能够找到p对数字，使得每对的差值都不超过这个候选答案

贪心策略：从左到右遍历排序后的数组，如果当前元素与下一个元素的差值不超过候选答案，就将它们配对，然后跳过这两个元素继续处理。这种策略是最优的，因为：

  • 排序后相邻元素的差值是最小的
  • 贪心选择不会影响后续的最优选择

算法步骤：

  1. 对数组进行排序
  2. 设定二分搜索的边界：left = 0, right = nums[n-1] - nums[0]
  3. 对于每个mid值，使用贪心策略检查是否能找到p对差值不超过mid的数对
  4. 根据检查结果调整搜索范围

代码实现

class Solution {
public:
    int minimizeMax(vector<int>& nums, int p) {
        if (p == 0) return 0;
        
        sort(nums.begin(), nums.end());
        int n = nums.size();
        
        int left = 0, right = nums[n - 1] - nums[0];
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (canFormPairs(nums, p, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
    
private:
    bool canFormPairs(vector<int>& nums, int p, int maxDiff) {
        int pairs = 0;
        int i = 0;
        
        while (i < nums.size() - 1) {
            if (nums[i + 1] - nums[i] <= maxDiff) {
                pairs++;
                i += 2; // 跳过这两个已配对的元素
                if (pairs >= p) return true;
            } else {
                i++;
            }
        }
        
        return pairs >= p;
    }
};

class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        if p == 0:
            return 0
        
        nums.sort()
        n = len(nums)
        
        left, right = 0, nums[n - 1] - nums[0]
        
        while left < right:
            mid = (left + right) // 2
            
            if self.canFormPairs(nums, p, mid):
                right = mid
            else:
                left = mid + 1
        
        return left
    
    def canFormPairs(self, nums: List[int], p: int, maxDiff: int) -> bool:
        pairs = 0
        i = 0
        
        while i < len(nums) - 1:
            if nums[i + 1] - nums[i] <= maxDiff:
                pairs += 1
                i += 2  # 跳过这两个已配对的元素
                if pairs >= p:
                    return True
            else:
                i += 1
        
        return pairs >= p

public class Solution {
    public int MinimizeMax(int[] nums, int p) {
        if (p == 0) return 0;
        
        Array.Sort(nums);
        int n = nums.Length;
        
        int left = 0, right = nums[n - 1] - nums[0];
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (CanFormPairs(nums, p, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
    
    private bool CanFormPairs(int[] nums, int p, int maxDiff) {
        int pairs = 0;
        int i = 0;
        
        while (i < nums.Length - 1) {
            if (nums[i + 1] - nums[i] <= maxDiff) {
                pairs++;
                i += 2; // 跳过这两个已配对的元素
                if (pairs >= p) return true;
            } else {
                i++;
            }
        }
        
        return pairs >= p;
    }
}

var minimizeMax = function(nums, p) {
    if (p === 0) return 0;
    
    nums.sort((a, b) => a - b);
    
    const canFormPairs = (maxDiff) => {
        let pairs = 0;
        let i = 0;
        while (i < nums.length - 1) {
            if (nums[i + 1] - nums[i] <= maxDiff) {
                pairs++;
                i += 2;
            } else {
                i++;
            }
        }
        return pairs >= p;
    };
    
    let left = 0;
    let right = nums[nums.length - 1] - nums[0];
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (canFormPairs(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n + n log(max-min))排序O(n log n)，二分搜索O(log(max-min))，每次验证O(n)
空间复杂度O(1)除了输入数组外，只使用常数额外空间

相关题目