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