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