577
правок
Изменения
→Варианты решения
Пусть даны два отсортированных массива <tex>A</tex> и <tex>B</tex> размерами <tex>n</tex> и <tex>m</tex> соответственно. Требуется найти <tex>k</tex>-ый порядковый элемент после их слияния. Будем считать, что все элементы в массивах различны.
== Варианты решения ==
=== Наивное решение за <tex>O(n + m)</tex> ===Сольем два массива и просто возьмем элемент с индексом <tex>k</tex>. Сливание будет выполнено за <tex>O(n + m)</tex>.=== Чуть менее наивное решение за <tex>O(k)</tex> ===
Будем использовать два указателя, с помощью которых сможем обойти массивы не сливая их. Поставим указатели на начало каждого из массивов. Будем увеличивать на единицу тот из них, который указывает на меньший элемент. После <tex>k</tex>-ого добавления сравним элементы, на которых стоят указатели. Меньший из них и будет ответом. Таким образом мы получим <tex>k</tex>-ый элемент за <tex>O(k)</tex> шагов.
