Найдите медиану для каждого элемента массива, исключив индекс, по которому вычисляется медиана.
Дан массив 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)