Максимизируйте медиану массива, сформированного путем добавления элементов двух других массивов.

Опубликовано: 26 Февраля, 2023

Даны два массива x[] и y[] из N целых чисел. Задача состоит в том, чтобы сформировать массив z[] из x[i] + y[j], (0 ≤i, j < N), и найти максимальное значение медиана z[], образованная оптимальной перестановкой.

Примеры :

Input: N = 5, x[] = {1, 2, 3, 5, 6}, y[] = {4, 7, 0, 9, 8}
Output: 12
Explanation: Let, z[] = { 1+0, 2+4, 5+7, 3+9, 6+8} = {1, 6, 12, 12, 14} 
to get maximum Median i.e., 12.

Input: N = 1, x[] = {11}, y[] = {12}
Output: 23

Подход : Проблема может быть решена на основе следующей идеи:

The idea is to sort the array, and 

  • For first half (before the median positions) the new array must has the smallest possible elements to just discard this half of elements from both the arrays,  
  • Then from median positions onwards, traverse from right end of 1st array, and from median position of 2nd array, moving in opposite directions,

Find the minimum element formed by sum of these elements, that minimum element will be the median of the new array.

Следуйте инструкциям, чтобы решить эту проблему:

  • Если N = 1, вернуть x[0]+ y[0], так как имеется только один элемент,
  • В противном случае выполните следующие действия
    • Сначала отсортируйте оба массива, а затем разделите массив от минимума до медианы-1 и от медианы до максимума,
    • Затем перейдите от медианы к максимуму и найдите сумму противоположных элементов, таких как x[медиана]+y[n-1], x[медиана+1]+y[n-2]…. до Макс.
    • Минимальная из этих сумм, рассчитанных выше, будет медианой нового массива.

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ