Question

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 <= 105
• 0 <= nums[i] <= 109
• 0 <= p <= (nums.length)/2

Solutions

Solution 1: Binary search + Greedy

We find that the maximum difference has the monotonicity, that is, if the maximum difference $x$ satisfies the condition, then $x-1$ must also satisfy the condition. Therefore, we can use the binary search method to find the smallest maximum difference that satisfies the condition.

We can sort the array nums, then enumerate the maximum difference $x$, and determine whether there are $p$ index pairs, where each index pair corresponds to the maximum value of the difference of the corresponding value. If it exists, we can reduce $x$, otherwise we can increase $x$.

Determine whether there are $p$ index pairs, where each index pair corresponds to the maximum value of the difference of the corresponding value, which can be achieved by using the greedy method. We traverse the array nums from left to right, and for the current traversed index $i$, if the difference between the number at the $i+1$ position and the number at the $i$ position is no more than $x$, then we can take the number at the $i$ and $i+1$ positions as an index pair, update the number of index pairs $cnt$, and then increase the value of $i$ by $2$. Otherwise, we will increase the value of $i$ by $1$. When the traversal is over, if the value of $cnt$ is greater than or equal to $p$, then it means that there are $p$ index pairs, where each index pair corresponds to the maximum value of the difference of the corresponding value, otherwise it means that it does not exist.

The time complexity is $O(n \times (\log n + \log m))$, where $n$ is the length of the array nums, and $m$ is the difference between the maximum value and the minimum value in the array nums. The space complexity is $O(1)$.

class Solution:
  def minimizeMax(self, nums: List[int], p: int) -> int:
    def check(diff: int) -> bool:
      cnt = i = 0
      while i < len(nums) - 1:
        if nums[i + 1] - nums[i] <= diff:
          cnt += 1
          i += 2
        else:
          i += 1
      return cnt >= p

    nums.sort()
    return bisect_left(range(nums[-1] - nums[0] + 1), True, key=check)

class Solution {
  public int minimizeMax(int[] nums, int p) {
    Arrays.sort(nums);
    int n = nums.length;
    int l = 0, r = nums[n - 1] - nums[0] + 1;
    while (l < r) {
      int mid = (l + r) >>> 1;
      if (count(nums, mid) >= p) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }

  private int count(int[] nums, int diff) {
    int cnt = 0;
    for (int i = 0; i < nums.length - 1; ++i) {
      if (nums[i + 1] - nums[i] <= diff) {
        ++cnt;
        ++i;
      }
    }
    return cnt;
  }
}

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

func minimizeMax(nums []int, p int) int {
  sort.Ints(nums)
  n := len(nums)
  r := nums[n-1] - nums[0] + 1
  return sort.Search(r, func(diff int) bool {
    cnt := 0
    for i := 0; i < n-1; i++ {
      if nums[i+1]-nums[i] <= diff {
        cnt++
        i++
      }
    }
    return cnt >= p
  })
}