Максимизируйте минимальную разницу между любой парой элементов, выбрав K элементов из заданного массива.

Учитывая массив N целых чисел, задача состоит в том, чтобы выбрать K элементов из этих N элементов таким образом, чтобы минимальная разница между каждым из K чисел была наибольшей. Возвращаться наибольшая минимальная разница после выбора любых K элементов.

Примеры:

Input: N = 4, K = 3, arr = [2, 6, 2, 5]
Output: 1
Explanation: 3 elements out of 4 elements are to be selected with a minimum difference as large as possible. Selecting 2, 2, 5 will result in minimum difference as 0. Selecting 2, 5, 6 will result in minimum difference as 6-5=1 

Input: N = 7, K = 4, arr = [1, 4, 9, 0, 2, 13, 3]
Output:  4
Explanation:  Selecting 0, 4, 9, 13 will result in minimum difference of 4, which is the largest minimum difference possible

Наивный подход: сгенерируйте все подмножества размера K и найдите минимальную разницу во всех из них. Затем верните максимум среди разностей.

Эффективный подход: данная проблема может быть эффективно решена с использованием метода бинарного поиска ответов. Для решения проблемы можно выполнить следующие шаги:

• Отсортировать массив в порядке возрастания
• Инициализировать минимальный ответ до 1
• Двоичный поиск используется в диапазоне от 1 до максимального элемента в массиве arr
• Переменная dif используется для хранения наибольшей минимальной разницы на каждой итерации.
• Вспомогательная функция используется для проверки возможности выбора K элементов с минимальной разницей, большей, чем разница , рассчитанная на предыдущей итерации. Если возможно, возвращается true, иначе возвращается false.
• Если вышеуказанная функция возвращает:
  • True, затем обновите ответ до dif и оставьте до dif + 1
  • False, затем обновить право на dif — 1

Ниже приведена реализация описанного выше подхода бинарного поиска.

Временная сложность: O(N * log N)
Сложность пространства: O(1)