Найдите медиану для каждого элемента массива, исключив индекс, по которому вычисляется медиана.

Опубликовано: 21 Сентября, 2022

Дан массив A[] из N целых чисел, где N четно, . задача состоит в том, чтобы сгенерировать массив медиан, где медиана массива вычисляется путем взятия медианы массива A[] , исключая A[i]-й элемент.

Примеры:

Input N = 4, A = [2, 4, 4, 3]
Output: [4, 3, 3, 4]
Explanation: Median after removing A[0]: New sorted array will be [3, 4, 4]. Median = 4. 
Median after removing A[1]: New sorted array will be [2, 3, 4]. Median = 3. 
Median after removing A[0]: New sorted array will be [2, 3, 4]. Median = 3. 
Median after removing A[0]: New sorted array will be [2, 4, 4]. Median = 4.

Input: N = 6, A = [5, 5, 4, 4, 3, 3]
Output: [4, 4, 4, 4, 4, 4]

Наивный подход: для каждого i в диапазоне [0, N) удалить текущий элемент и отсортировать оставшийся массив, а затем вычислить медиану нового массива.
Временная сложность: O(N*N*log(N))
Вспомогательное пространство: O(N)

Эффективный подход: поскольку N четно, в текущем массиве есть два центральных элемента, которые могут быть медианой текущего массива. При удалении любого из элементов будет нечетное количество элементов, и один из центральных элементов всегда будет ответом. Обозначим два центральных значения как L и R . Возможны 2 случая: когда текущий A[i] <=L , тогда R будет конечной медианой массива. В противном случае, когда текущий A[i] >= R , L будет конечной медианой массива. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте массив B[] для хранения исходных позиций элементов в массиве.
  • Переберите диапазон [0, N), используя переменную i , и выполните следующие шаги:
    • Сохраните A[i] в новом массиве B[i].
  • Отсортируйте массив A[] , чтобы найти центральные элементы.
  • Переберите диапазон [0, N), используя переменную i , и выполните следующие шаги:
    • Если B[i] меньше L, то R будет медианой массива без A[i].
    • В противном случае L будет необходимой медианой.

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


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

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