Задача с собеседования в Zeta

Задача с собеседования в 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