Как найти медиану M отсортированных массивов целых чисел? Где размер каждого массива ограничен N. Предположим, что каждый массив содержит отсортированные целочисленные элементы.Как найти медиану m отсортированных массивов?
Существует два варианта этого вопроса.
Я просто дать подсказку так, которого не упомянуть, что вы испробовали:
1. Create a min heap (MIN-HEAPIFY) using all the 0-th element of the m arrays
2. Extract min and add an element into the heap from the array from which the min was extracted
3. Assuming all m arrays are of n length EXTRACT-MIN from heap till you get m*n/2 elements.
Попытка доказать, как это решение работает и придумать код.
Я думал, что такой же ответ, но сложность в таком случае - Create Heap O (M) + извлечение MN/2 элементов из кучи вызовет сложность MNlogM, поэтому общая сложность будет O (MNlogM). Я ищу что-то лучшее. – rgaut
Извлечение одного элемента min из кучи будет O (lgM), поэтому извлечение элемента n/2 будет O (NlgM). Ссылка: Введение К алгоритмам Cormen et al. Heapsort Chapter, HEAP-EXTRACT-MAX алгоритм –
Хммм Сколько элементов вы извлекаете из кучи ??? MN/2 правильно? Вам нужно вызвать extract-MIN MN раз, и каждый вызов будет стоить logM, поэтому итогом будет MNlogM. – rgaut
Итак, вы ищете единственную медиану конкатенации отсортированных массивов 'm'? что ты уже испробовал? – Teepeemm
Что такое 'm sorted array'? – alfasin
@teepeemm Прошу прощения за плохую формулировку. Я обновил вопросы. Я попытался расширить алгоритм медианы двух отсортированных массивов разного размера. Но не смог достичь определенной сложности. – rgaut