#11. Слияние двух упорядоченных списков | Алгоритмы на Python
HTML-код
- Опубликовано: 27 сен 2024
- Рассматривается эффективный алгоритм слияния двух упорядоченных списков в третий, так, чтобы результирующий список тоже был упорядоченным. Приведена реализация этого алгоритма на языке Python.
algorithm-merge-lists.py: github.com/sel...
Спасибо большое за то, что показали как можно ещё реализовать данный алгоритм!
спасибо огромное за объяснение. Все доступным языком без усложнений
Спасибо, Сергей!
Спасибо, все подробно разжевываете!
Благодарю за подробное объяснение! 👍
блин
я через попу нулевых элементов реализовывал
хотя через указатели мне кажется более программистским подходом
спасибо, Сергей, за науку!
Через указатели быстрее.
result = []
while a and b:
result.append(a.pop(0) if a[0] < b[0] else b.pop(0))
result.extend(a if len(a) >0 else b)
Возможно будет ещё быстрее если переносить не по 1 числу, а кусками. Т.е например 2,7,8 и 1,3,4,5,6,9 тут числа 3,4,5,6 можно перенести одной командой. Но нужно искать такие куски.
Удивительно, но факт. Формирование такого списка намного (на порядок или чуть больше) дольше, чем конкатенация (или расширение) двух списков, а затем их сортировка с помощью метода списков sort() или встроенной функции sorted().
Причина в механике метода append().
Для С++ такая сортировка, наверное, годится, но для Python - неоптимальное решение.
Если программу запустить 2 раза, то к предыдущему выводу добавится еще один такой же список. И так можно делать до бесконечности. То есть сначала ответом был список: с. Запустили еще раза прогу: на выводе уже две "с". Сколько раз запускаешь прогу столько списков "с" и будет.
ну так напиши функцию, которая работает не с самим списком, а с его копией
Я не понимаю, а как программа знает о том, что счетчик i принадлежит первому списку, а счетчик j ко второму списку?
Учусь программированию пока по этому каналу для того, чтобы потом брать какие-либо заказы на фрилансе. У меня вопрос, достаточно ли того, что предлагает здесь автор на своём канале, чтобы выполнять какие-либо маленькие заказы? Потому что я не знаю, какие именно нужны практические знания для этого. может быть посоветуете хороший курс? желательно по с++.
По основам С++ здесь тоже есть курс ruclips.net/p/PLA0M1Bcd0w8zHoZcf7IWTM4aQESDSErUs
@@selfedu_rus понимаю, сейчас его и прохожу. Но этого же явно недостаточно. Я хотел спросить, на что в С++ стоит сделать упор, что для работы с заказами желательно знать ещё и возможно ли обойтись только С++ или питон всё равно нужен как минимальные требования. Спасибо!
@@chopik612 Одного С++ явно мало, нужно знать библиотеки, как правило, STL + графика + интерфейс. И, конечно же, опыт программирования хотя бы на своих задачках + стандартные алгоритмические подходы + паттерны проектирования.
@@selfedu_rus спасибо, это уже конкретнее. А вот что понимается под "графикой" и "интерфейс", на канале это есть?
@@chopik612 графика - это OpenGL или DirectX или просто умение рисовать в клиентском окне. Интерфейс - это программы с окнами, менюшками, диалоговыми окнами и т.п.
Какая сложность алгоритма?
O(N)
@@selfedu_rus разве не O(n+m)? К слову, на литкоде есть такая же задача уровня хард, но там требование выполнить ее за O(log n+m). Как это сделать? Бинарным деревом как-то?
Всегда интересно.
Спасибо за понятное объяснение.
а если нужно получить массив по возрастанию из двух массивов по убыванию
запишите элементы в обратном порядке и все
Если сразу добавлять оба равных элемента в список, то это будет меньше итераций.
И если в списках много одинаковых элементов, то выигрыш будет существенный.
while i < N and j < M:
if a[i] == b[j]:
c.append(a[i])
c.append(b[j])
i += 1
j += 1
elif a[i] < b[j]:
c.append(a[i])
i += 1
elif a[i] > b[j]:
c.append(b[j])
j += 1
Спасибо огромное. Отличная подача материала!