Возьмите элементы K и максимизируйте минимальное расстояние

Question

Учитывая массив из N элементов, мы можем выбрать K позиций из N. Но нам нужно выбрать K позиций таким образом, чтобы, если мы возьмем любую из двух выбранных позиций, скажем, i и j, чем минимальная разница (A [i] -A [j]) для всех пар i и j, принадлежащих K, выбранные индексы должны быть максимально возможными.

Пример:

Пусть N = 3 и массив будет = [3 9 6 11 15 20 23] и К = 3

, то здесь ответ 8, как один из возможных способов является то можно выбрать [3,11,23] или [3,15,23]

Я просто хочу знать, может ли это быть какой-то жадный подход к этой проблеме? Или подход O (N) или O (N * log N)?

Я знаю грубое решение для этого. Но я не думаю, что публикация здесь была бы хорошей идеей, так как ее очень неэффективно.

Ограничения:

1 ≤ N ≤ 10^5 
1 ≤ K ≤ 10^7 

Answer 1

1. Sort the numbers 
2. Pick first two numbers with maximum difference between them. 
3. For i = 3 to k 
    3.1 Pick the number that has maximum difference 

Пример

1. [3 9 6 11 15 20 23] -> [3 6 9 11 15 20 23] 
2. [3 23] 
3. Pick 11 or 15 

Complexity = O(N log N) [(K + N) авторизуйтесь N]

Answer 2

Вы могли бы сделать это, используя деление пополам на значение максимальная разница.

Сначала соберите элементы в массиве.

Затем выберите значение для максимальной разности, давайте назовем его D.

Выберите наименьший элемент в массиве, а затем пройти через массив, пока мы не достигли расстояния D от этого числа, и выберите следующий номер. Повторяйте это, пока мы не достигнем конца массива.

Этот процесс выберет определенное количество значений из массива, которое может быть больше или меньше K. Затем вы можете использовать bisection на D, чтобы найти наибольшее значение D, которое позволяет вам выбрать не менее K элементов.

Например, с помощью [3 6 9 11 15 20 23] можно сначала выбрать разность 5:

[3 6 9 11 15 20 23 ] 
D=5: 3 9 11 20 => 4 chosen too high so increase D 
D=10: 3 15 => 2 chosen too low so decrease D 
D=8: 3 11 20 => 3 chosen