leetcode - 2616. Minimize the Maximum Difference of Pairs-Toy模板网

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

Description

You are given a 0-indexed integer array nums and an integer p. Find p pairs of indices of nums such that the maximum difference amongst all the pairs is minimized. Also, ensure no index appears more than once amongst the p pairs.

Note that for a pair of elements at the index i and j, the difference of this pair is |nums[i] - nums[j]|, where |x| represents the absolute value of x.

Return the minimum maximum difference among all p pairs. We define the maximum of an empty set to be zero.

Example 1:

Input: nums = [10,1,2,7,1,3], p = 2
Output: 1
Explanation: The first pair is formed from the indices 1 and 4, and the second pair is formed from the indices 2 and 5. 
The maximum difference is max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1. Therefore, we return 1.

Example 2:

Input: nums = [4,2,1,2], p = 1
Output: 0
Explanation: Let the indices 1 and 3 form a pair. The difference of that pair is |2 - 2| = 0, which is the minimum we can attain.

Constraints:

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9
0 <= p <= (nums.length)/2

Solution

Think reversely, try to find a boundary, and see how many pairs we have that the distance is below or equals to boundary. If the number is larger than p, then we could shrink the boundary.

Use binary search, left = 0, right = max(nums) - min(nums).

Time complexity: $o(\log(\max(nums) - \min(nums) * n)$
Space complexity: $o (1)$ 文章来源地址https://www.toymoban.com/news/detail-636786.html

Code

class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        nums.sort()
        left, right = 0, nums[-1] - nums[0]
        while left < right:
            mid = (left + right) >> 1
            # find how many pairs that are smaller than mid
            index = 0
            k = 0
            while index < len(nums) - 1:
                if abs(nums[index] - nums[index + 1]) <= mid:
                    k += 1
                    index += 2
                else:
                    index += 1
            if k >= p:
                right = mid
            else:
                left = mid + 1
        return (left + right) >> 1