Поиск 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>. Сливание будет выполнено за  <tex>O(n + m)</tex>.
 
Сольем два массива и просто возьмем элемент с индексом <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:19, 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] шагов.