Код Senior Куча обновлено
Слияние k отсортированных массивов
Условие
Слей k отсортированных массивов в один отсортированный.
Примеры
mergeK([[1, 4], [2, 3], [5]]) // [1, 2, 3, 4, 5]
mergeK([]) // []
mergeK([[], [1]]) // [1]
Как подойти
Прямое решение за O(n·k). Улучшение - min-куча размера k даёт O(n log k), это и есть ожидаемый follow-up. Начни с понятного варианта, сложность назови сам.
Подсказки: 2
- Веди указатель на текущий элемент каждого массива.
- На каждом шаге бери минимальный из текущих.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.