Это выполняется за время O (NlgM), где N - общее количество элементов, а M - количество списков.
зуйте алгоритм для объединения произвольного количества отсортированных списков в один отсортированный список. Цель состоит в том, чтобы создать самую маленькую рабочую программу на любом языке, который вам нравится.
Например:
input: ((1, 4, 7), (2, 5, 8), (3, 6, 9))
output: (1, 2, 3, 4, 5, 6, 7, 8, 9)
input: ((1, 10), (), (2, 5, 6, 7))
output: (1, 2, 5, 6, 7, 10)
Запись: решения, которые объединяют входные списки, а затем используют предоставляемую языком функцию сортировки, не соответствуют духу гольфа и не будут приняты:
sorted(sum(lists,[])) # cheating: out of bounds!
Помимо всего прочего, ваш алгоритмдолжен Быть (но не должно быть) намного быстрее!
Четко сформулируйте язык, любые недостатки и количество символов. Включайте в счет только значащие символы, но не стесняйтесь добавлять пробелы в код для художественных / читабельных целей.
Чтобы сохранить порядок, предложите улучшить комментарии или отредактировать ответы, где это уместно, вместо того, чтобы создавать новый ответ для каждой «редакции».
РЕДАКТИРОВАТЬ: если бы я снова отправлял этот вопрос, я бы расширил правило «сортировка без языка», чтобы «не объединять все списки, а сортировать результат». Существующие записи, которые выполняют конкатенацию-затем-сортировку, на самом деле очень интересны и компактны, поэтому я не буду активно вводить правило, которое они нарушают, но не стесняюсь работать с более ограничительной спецификацией в новых представлениях.