Поиск k-ой порядковой статистики в двух массивах — различия между версиями

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

Версия 18:57, 13 апреля 2015

Постановка задачи

Пусть даны два отсортированных массива [math]A[/math] и [math]B[/math] размерами [math]n[/math] и [math]m[/math] соответственно. Требуется найти [math]k[/math]-ый порядковый элемент после их слияния. Будем считать, что все элементы в массивах различны и нумеруются с нуля.

Варианты решения

Наивное решение

Сольем два массива и просто возьмем элемент с индексом [math]k[/math]. Сливание будет выполнено за [math]O(n + m)[/math].

Чуть менее наивное решение

Будем использовать два указателя, с помощью которых сможем обойти массивы не сливая их. Поставим указатели на начало каждого из массивов. Будем увеличивать на единицу тот из них, который указывает на меньший элемент. После [math]k[/math]-ого добавления сравним элементы, на которых стоят указатели. Меньший из них и будет ответом. Таким образом, мы получим [math]k[/math]-ый элемент за [math]O(k)[/math] шагов.

Совсем не наивное решение

Оба решения, приведенные выше, работают за линейное время, то есть приемлемо работают только при небольших значениях [math]k[/math]. Следующее решение работает за [math]O(log(n) + log(m))[/math]