Skip to content

Latest commit

 

History

History
183 lines (145 loc) · 5.78 KB

README.md

File metadata and controls

183 lines (145 loc) · 5.78 KB
Raw
comments difficulty edit_url rating source tags
true
中等
2155
第 340 场周赛 Q3
贪心
数组
二分查找

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

English Version

题目描述

给你一个下标从 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

解法

方法一：二分查找 + 贪心

我们注意到，最大差值具备单调性，即如果最大差值 $x$ 满足条件，那么 $x-1$ 也一定满足条件。因此我们可以使用二分查找的方法，找到最小的满足条件的最大差值。

我们可以将数组 nums 排序，然后枚举最大差值 $x$，判断是否存在 $p$ 个下标对，每个下标对对应数值取差值的最大值不超过 $x$。如果存在，那么我们就可以将 $x$ 减小，否则我们就将 $x$ 增大。

判断是否存在 $p$ 个下标对，每个下标对对应数值取差值的最大值不超过 $x$，可以使用贪心的方法。我们从左到右遍历数组 nums，对于当前遍历到的下标 $i$，如果 $i+1$ 位置的数与 $i$ 位置的数的差值不超过 $x$，那么我们就可以将 $i$ 和 $i+1$ 位置的数作为一个下标对，更新下标对的数量 $cnt$，然后将 $i$ 的值增加 $2$。否则，我们就将 $i$ 的值增加 $1$。遍历结束，如果 $cnt$ 的值大于等于 $p$，那么就说明存在 $p$ 个下标对，每个下标对对应数值取差值的最大值不超过 $x$，否则就说明不存在。

时间复杂度 $O(n \times (\log n + \log m))$，其中 $n$ 是数组 nums 的长度，而 $m$ 是数组 nums 中的最大值与最小值的差值。空间复杂度 $O(1)$。

Python3

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)

Java

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;
    }
}

C++

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;
    }
};

Go

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
	})
}