题目描述
给你一个下标从 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
解法
方法一：二分查找 + 贪心
我们注意到，最大差值具备单调性，即如果最大差值 \(x\) 满足条件，那么 \(x-1\) 也一定满足条件。因此我们可以使用二分查找的方法，找到最小的满足条件的最大差值。
我们可以将数组 \(\textit{nums}\) 排序，然后枚举最大差值 \(x\)，判断是否存在 \(p\) 个下标对，每个下标对对应数值取差值的最大值不超过 \(x\)。如果存在，那么我们就可以将 \(x\) 减小，否则我们就将 \(x\) 增大。
判断是否存在 \(p\) 个下标对，每个下标对对应数值取差值的最大值不超过 \(x\)，可以使用贪心的方法。我们从左到右遍历数组 \(\textit{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\) 是数组 \(\textit{nums}\) 的长度，而 \(m\) 是数组 \(\textit{nums}\) 中的最大值与最小值的差值。空间复杂度 \(O(1)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | 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)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | 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
})
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | function minimizeMax(nums: number[], p: number): number {
nums.sort((a, b) => a - b);
const n = nums.length;
let l = 0,
r = nums[n - 1] - nums[0] + 1;
const check = (diff: number): boolean => {
let cnt = 0;
for (let i = 0; i < n - 1; ++i) {
if (nums[i + 1] - nums[i] <= diff) {
++cnt;
++i;
}
}
return cnt >= p;
};
while (l < r) {
const mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | impl Solution {
pub fn minimize_max(mut nums: Vec<i32>, p: i32) -> i32 {
nums.sort();
let n = nums.len();
let (mut l, mut r) = (0, nums[n - 1] - nums[0] + 1);
let check = |diff: i32| -> bool {
let mut cnt = 0;
let mut i = 0;
while i < n - 1 {
if nums[i + 1] - nums[i] <= diff {
cnt += 1;
i += 2;
} else {
i += 1;
}
}
cnt >= p
};
while l < r {
let mid = (l + r) / 2;
if check(mid) {
r = mid;
} else {
l = mid + 1;
}
}
l
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | public class Solution {
public int MinimizeMax(int[] nums, int p) {
Array.Sort(nums);
int n = nums.Length;
int l = 0, r = nums[n - 1] - nums[0] + 1;
bool check(int diff) {
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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 | class Solution {
/**
* @param Integer[] $nums
* @param Integer $p
* @return Integer
*/
function minimizeMax($nums, $p) {
sort($nums);
$n = count($nums);
$l = 0;
$r = $nums[$n - 1] - $nums[0] + 1;
$check = function ($diff) use ($nums, $n, $p) {
$cnt = 0;
for ($i = 0; $i < $n - 1; ++$i) {
if ($nums[$i + 1] - $nums[$i] <= $diff) {
++$cnt;
++$i;
}
}
return $cnt >= $p;
};
while ($l < $r) {
$mid = intdiv($l + $r, 2);
if ($check($mid)) {
$r = $mid;
} else {
$l = $mid + 1;
}
}
return $l;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | class Solution {
func minimizeMax(_ nums: [Int], _ p: Int) -> Int {
var nums = nums.sorted()
let n = nums.count
var l = 0
var r = nums[n - 1] - nums[0] + 1
func check(_ diff: Int) -> Bool {
var cnt = 0
var i = 0
while i < n - 1 {
if nums[i + 1] - nums[i] <= diff {
cnt += 1
i += 2
} else {
i += 1
}
}
return cnt >= p
}
while l < r {
let mid = (l + r) >> 1
if check(mid) {
r = mid
} else {
l = mid + 1
}
}
return l
}
}
|