Подтвердить что ты не робот

Объединение сортированных массивов

Возможные дубликаты:
Объединение двух отсортированных списков
Алгоритм слияния N-way

При заданных k отсортированных массивах каждой длины n постройте один объединенный и отсортированный массив. Сфокусируйтесь на времени выполнения и сложности пространства.

Источник: вопрос интервью Amazon.
Есть предположения? спасибо

4b9b3361

Ответ 1

Сделайте кучу из первого элемента в каждом массиве. Поместите элемент головы из кучи, вставьте его в массив результатов и затем возьмите следующий элемент из массива, из которого вышла голова кучи, и вставьте его в кучу. Повторяйте, пока не будете потреблять все массивы.