class Solution {
public:
int minimizeMax(vector<int>& nums, int p) {
}
};
6359. 最小化数对的最大差值
给你一个下标从 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 <= 1050 <= nums[i] <= 1090 <= p <= (nums.length)/2原站题解
golang 解法, 执行用时: 116 ms, 内存消耗: 9.4 MB, 提交时间: 2023-04-11 09:47:07
func minimizeMax(nums []int, p int) int {
sort.Ints(nums)
return sort.Search(1e9, func(mx int) bool {
cnt := 0
for i := 0; i < len(nums)-1; i++ {
if nums[i+1]-nums[i] <= mx { // 都选
cnt++
i++
}
}
return cnt >= p
})
}
java 解法, 执行用时: 17 ms, 内存消耗: 55.9 MB, 提交时间: 2023-04-11 09:46:49
class Solution {
public int minimizeMax(int[] nums, int p) {
Arrays.sort(nums);
int n = nums.length, left = -1, right = nums[n - 1] - nums[0]; // 开区间
while (left + 1 < right) { // 开区间
int mid = (left + right) >>> 1, cnt = 0;
for (int i = 0; i < n - 1; ++i)
if (nums[i + 1] - nums[i] <= mid) { // 都选
++cnt;
++i;
}
if (cnt >= p) right = mid;
else left = mid;
}
return right;
}
}
python3 解法, 执行用时: 656 ms, 内存消耗: 29.3 MB, 提交时间: 2023-04-11 09:46:35
# 二分 + 贪心
class Solution:
def minimizeMax(self, nums: List[int], p: int) -> int:
nums.sort()
def f(mx: int) -> int:
cnt = i = 0
while i < len(nums) - 1:
if nums[i + 1] - nums[i] <= mx: # 都选
cnt += 1
i += 2
else: # 不选 nums[i]
i += 1
return cnt
return bisect_left(range(nums[-1] - nums[0]), p, key=f)