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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Варианты решения)
(Варианты решения)
Строка 11: Строка 11:
  
 
Чтобы получить логарифмическую сложность, будем использовать бинарный поиск, который вдвое сокращает область поиска с каждой итерацией. То есть для достижения нужной сложности мы должны на каждой итерации вдвое сокращать круг поиска в каждом из массивов.
 
Чтобы получить логарифмическую сложность, будем использовать бинарный поиск, который вдвое сокращает область поиска с каждой итерацией. То есть для достижения нужной сложности мы должны на каждой итерации вдвое сокращать круг поиска в каждом из массивов.
 +
 +
Рассмотрим следующую ситуацию: пусть у нас есть элемент <tex>a[i]</tex> из массива <tex>A</tex> и элемент <tex>b[j]</tex> из массива <tex>B</tex> и они связаны неравенством <tex>b[j - 1] < a[i] < b[j]</tex>.Тогда <tex>a[i]</tex> есть <tex>(j + i + 1)</tex>-ый порядковый элемент после слияния массивов. Это объясняется тем, что до <tex>a[i]</tex>-ого элемента идут <tex>(j - 1)</tex> элемент из массива <tex>B</tex>, <tex>i</tex> элементов из массива <tex>A</tex> (включая сам элемент <tex>a[i]</tex>) и так как индексация массивов начинается с нуля, то необходимо прибавить еще <tex>2</tex>. В итоге получаем <tex>(j - 1) + i + 2 = j + i + 1</tex>.

Версия 20:48, 14 апреля 2015

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

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

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

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

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

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

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

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

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

Чтобы получить логарифмическую сложность, будем использовать бинарный поиск, который вдвое сокращает область поиска с каждой итерацией. То есть для достижения нужной сложности мы должны на каждой итерации вдвое сокращать круг поиска в каждом из массивов.

Рассмотрим следующую ситуацию: пусть у нас есть элемент [math]a[i][/math] из массива [math]A[/math] и элемент [math]b[j][/math] из массива [math]B[/math] и они связаны неравенством [math]b[j - 1] \lt a[i] \lt b[j][/math].Тогда [math]a[i][/math] есть [math](j + i + 1)[/math]-ый порядковый элемент после слияния массивов. Это объясняется тем, что до [math]a[i][/math]-ого элемента идут [math](j - 1)[/math] элемент из массива [math]B[/math], [math]i[/math] элементов из массива [math]A[/math] (включая сам элемент [math]a[i][/math]) и так как индексация массивов начинается с нуля, то необходимо прибавить еще [math]2[/math]. В итоге получаем [math](j - 1) + i + 2 = j + i + 1[/math].