最小化数对的最大差值

标签: 贪心 数组 二分查找

难度: Medium

给你一个下标从 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 <= 105
  • 0 <= nums[i] <= 109
  • 0 <= p <= (nums.length)/2

Submission

运行时间: 205 ms

内存: 30.4 MB

class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        nums.sort()
        diff = []
        if p == 0:
            return 0
        for i in range(1,len(nums)):
            diff.append(nums[i]-nums[i-1])
        def check(upper):
            i = 0
            count = 0
            while i < len(diff):
                if diff[i] <= upper:
                    count += 1
                    i += 2
                else:
                    i += 1
            return count >= p
        ans = bisect_left(range(min(diff),max(diff)+1),True,key = check) + min(diff)
        return ans

Explain

首先将数组排序，然后计算相邻元素的差值存入diff数组。如果p为0，则直接返回0。定义一个检查函数check，用于检查是否能找到p个差值小于等于upper的数对。使用二分查找在diff的最小值和最大值之间寻找满足条件的最小upper值，并返回该值加上diff的最小值作为结果。

时间复杂度: O(nlogn)

空间复杂度: O(n)

class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        nums.sort()
        diff = []
        if p == 0:
            return 0
        for i in range(1,len(nums)):
            diff.append(nums[i]-nums[i-1])
        def check(upper):
            i = 0
            count = 0
            while i < len(diff):
                if diff[i] <= upper:
                    count += 1
                    i += 2
                else:
                    i += 1
            return count >= p
        ans = bisect_left(range(min(diff),max(diff)+1),True,key = check) + min(diff)
        return ans

Explore

在实现中首先对数组进行排序是为了使得元素之间的差值计算能够反映出实际上可能组成数对的元素。排序确保了当我们计算相邻元素之间的差值时，这些差值是最小的可能差值，有助于我们后续的处理和判断。排序的正确性在于它允许我们只考虑相邻元素之间的差值，简化了问题的复杂度。对于算法的效率，排序是O(n log n)，这可能是整个算法中最耗时的部分，但它是实现算法目标的必要步骤。

在构建diff数组时，只计算相邻元素之间的差值是基于已经进行了排序的前提。排序后的数组中，任何两个非相邻元素之间的差值都会大于或等于它们之间任何相邻元素对的差值。因此，关注相邻元素的差值就足够了，这样可以简化问题而不影响结果的正确性。这种方法确实可以帮助找到全局最优的下标对，因为在排序数组中，最小的差值总是来自相邻元素。

check函数中的做法（每次跳过一个元素，即`i += 2`）是为了确保每次计数的数对之间没有重叠。这是因为每个数对涉及到两个元素（即当前元素和它的下一个元素），通过跳过一个元素的方式，我们可以保证每次选取的数对是独立的，不会有共享的元素。这样做确实可以保证每个元素最多只被使用一次，从而避免了重复使用任何下标。

二分查找的目的是寻找能够使得至少p对数的差值小于等于upper的最小可能upper值。但是，这个upper值是基于差值数组diff的相对值（即差值与最小差值之间的差）。因此，为了转换成原数组nums中数对的实际差值，需要将找到的这个最小upper值加上差值数组中的最小值（min(diff)）。这样做是因为我们的upper是基于最小差值上的增量，所以加上最小差值才能恢复到原始数对差值的上下文中。