Максимизируйте медиану массива, образованного из соседнего максимума перестановки

Вам дано X[] длины 2*N , где N всегда будет нечетным, задача состоит в том, чтобы построить массив Y[] длины N из перестановки X[] такой, что Элемент Y[] равен max(X _i , X _i+1 ), а i всегда является четным индексом (индексирование на основе 0), а медиана нового массива максимально возможна.

Примеры:

Input: N = 1, X[] = {1, 2} 
Output: X[] = {2, 1}, Median = 2
Explanation: Y[] =  { max(X[1],  X[2]) }, Y[] = {2}.
Median of Y[] = 2, 2 is the maximum possible value of median that can achieve by arrange elements of X[].

Input: N = 3,   X[] = {1, 2, 3, 4, 5, 6}
Output: X[] = {3, 1, 2, 5, 6, 4}, Median = 5
Explanation: Y[] = { max(3, 1), max(2, 5), max(6, 4) }, Y[] = {3, 5, 6}.
Median of Y[] = 5,   5 is the maximum possible value of median that can achieve by arrange elements of X[].

Подход: Реализуйте идею ниже, чтобы решить проблему:

Sort X[], put its left half part on even indices in arrangement and right half elements at odd indices of arrangement. For value of maximum value of median can be get by printing middle element of right half X[] after performing sorting.

Иллюстрация подхода:

Consider N = 3,  X[] = {1, 2, 3, 4, 5, 6}

After sorting X[] will be: {1, 2, 3, 4, 5, 6}. Let the new Arrangement: {A₁, A₂,  A₃, A₄, A₅, A₆}

• Put left half X[] = {1, 2, 3}  on odd indices of new Arrangement, Then Arrangement: {1, A_2, 2, A_4, 3, A₆}
• Put right half X[] = {4, 5, 6}  on even indices of new Arrangement. Then, Arrangement: {1, 4, 2, 5, 3, 6}

Now, It can be verified that Y[] will be = {4, 5, 6}, 5 is maximum possible median and value 5 is at middle of right half of X[] = {4, 5, 6} 

Для реализации идеи выполните следующие шаги:

• Сортировка X[].
• Создайте новый массив той же длины.
• Поместите левую половину X[] на нечетные индексы новой аранжировки.
• Положите правую половину X[] на четные индексы новой аранжировки.
• Распечатайте расположение нового массива.
• Возвращает средний элемент правой половины X[] для максимально возможного значения.

Ниже приведена реализация подхода.

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

Статьи по Теме:

• Введение в массивы — учебные пособия по структуре данных и алгоритмам
• Алгоритмы сортировки