Поиск k-ой порядковой статистики в двух массивах — различия между версиями
Анна (обсуждение | вклад) (→Наивное решение за O(n + m)) |
Анна (обсуждение | вклад) (→Наивное решение за O(n + m)) |
||
| Строка 1: | Строка 1: | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть даны два отсортированных массива <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>O(n + m)</tex> == | + | == Варианты решения == |
| + | === Наивное решение за <tex>O(n + m)</tex> === | ||
Сольем два массива и просто возьмем элемент с индексом <tex>k</tex>. Сливание будет выполнено за O(n + m). | Сольем два массива и просто возьмем элемент с индексом <tex>k</tex>. Сливание будет выполнено за O(n + m). | ||
Версия 18:01, 13 апреля 2015
Постановка задачи
Пусть даны два отсортированных массива и размерами и соответственно. Требуется найти -ый порядковый элемент после их слияния. Будем считать, что все элементы в массивах различны.
Варианты решения
Наивное решение за
Сольем два массива и просто возьмем элемент с индексом . Сливание будет выполнено за O(n + m).
