Задача с собеседования в Zeta
Дан целочисленный массив nums, индексированный с 0, и целое число p. Найдите p пар индексов массива nums так, чтобы максимальная разность среди всех этих пар была минимальна. Гарантируется, что ни один индекс не используется более одного раза среди всех p пар.
Обратите внимание, что для пары элементов с индексами i и j разность этой пары равна |nums[i] - nums[j]|, где |x| обозначает абсолютное значение x.
Верните минимально возможное значение максимальной разницы среди всех p пар.
Максимум пустого множества считается равным 0.
Пример 1:
Input: nums = [10,1,2,7,1,3], p = 2
Output: 1
Explanation: Первая пара образована индексами 1 и 4, вторая - индексами 2 и 5. Максимальная разность составляет max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1. Следовательно, возвращаем 1.
Пример 2:
Input: nums = [4,2,1,2], p = 1
Output: 0
Explanation: Пусть индексы 1 и 3 формируют пару. Разность для этой пары равна |2 - 2| = 0, что является минимально возможным значением.
Ограничения:
1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹
0 <= p <= (nums.length) / 2
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Необходимо найти минимальный x, при котором можно сформировать p пар с разностью <= x.
Свойство монотонно: если можно составить p пар с максимальной разностью x, то можно и с любой разностью > x (ограничение слабее). Если нельзя с x, то нельзя и с меньшей разностью (ограничение жёстче).
Существует граница между значениями, где условие выполнено, и где это невозможно. Границу можно найти бинарным поиском: будем перебирать значение x (максимально допустимую разность) в диапазоне от 0 до максимально возможной разности в массиве.
Для проверки конкретного значения создаём функцию can_form_pairs(max_diff), где max_diff - текущий кандидат на максимально допустимую разность в паре. Используя жадный алгоритм, проверяем, можно ли сформировать p пар.
pairs - счётчик пар
i - текущий индекс
Проходим по массиву:
- Если разность между соседними числами (i и i+1) <= max_diff: засчитываем пару и пропускаем использованный эл-т: i += 2;
- Иначе: пропускаем текущий эл-т: i += 1.
Жадный выбор оптимален:
- Если разность подходит: если не взять пару (i, i+1), nums[i] не сможет образовать пару с кем-либо ещё - эл-ты правее i+1 дадут разность больше. Формируя пару (i, i+1), i+1 теперь не сможет составить пару с i+2, но разность в этой паре была бы не меньше текущей. Значит, общее кол-во возможных пар не уменьшается.
- Если разность не подходит: nums[i] не сможет сформировать пару - разность с любым последующим эл-м ещё больше.
Если сформировали p пар - max_diff допустим: True.
Иначе: False.
Применяем бинпоиск на предварительно отсортированном массиве. В отсортированном массиве оптимальные пары всегда состоят из соседних эл-в.
Диапазон: от left = 0 до right = nums[-1] - nums[0]
Пока left < right:
- вычисляем середину;
- проверяем середину с помощью функции can_form_pairs(mid):
если True: текущее ограничение выполнимо, пробуем уменьшить: right = mid.
иначе: слишком маленькое, left = mid + 1.
Возвращаем left со значением искомого минимума.
Сложность
O(n log n + n log m) - по времени (сортировка - O(n log n), бинпоиск - O(log m) итераций (где m - разность между максимумом и минимумом), на каждой - проверка за O(n))
O(1) - по памяти (храним некоторое кол-во переменных)
Код
class Solution:
def minimizeMax(self, nums: List[int], p: int) -> int:
def can_form_pairs(max_diff: int) -> bool:
pairs = 0
i = 0
while i < len(nums) - 1 and pairs < p:
if nums[i+1] - nums[i] <= max_diff:
pairs += 1
i += 2
else:
i += 1
return pairs >= p
nums.sort()
left = 0
right = nums[-1] - nums[0]
while left < right:
mid = (left + right) // 2
if can_form_pairs(mid):
right = mid
else:
left = mid + 1
return left
@algoses
7
2
2August 12, 2026 2.6K 9
