577
правок
Изменения
Нет описания правки
== Варианты решения ==
=== Наивное решение ===
Сольем два массива и просто возьмем элемент с индексом <tex>k </tex> {{- --}} <tex>1</tex>. Сливание будет выполнено за <tex>O(n + m)</tex> c использованием дополнительной памяти, что является существенным недостатком.
=== Чуть менее наивное решение ===
Будем использовать два указателя, с помощью которых сможем обойти массивы не сливая их. Поставим указатели на начало каждого из массивов. Будем увеличивать на единицу тот из них, который указывает на меньший элемент. После <tex>(k </tex> {{- --}} <tex>1)</tex>-ого добавления сравним элементы, на которых стоят указатели. Меньший из них и будет ответом. Таким образом, мы получим <tex>k</tex>-ый элемент за <tex>O(k)</tex> шагов.
=== Совсем не наивное решение ===
Оба решения, приведенные выше, работают за линейное время, то есть приемлемы только при небольших значениях <tex>k</tex>. Следующее решение работает за <tex>O(log(n) + log(m))</tex>.
Чтобы получить логарифмическую сложность, будем использовать [[Целочисленный двоичный поиск|бинарный поиск]], который сокращает область поиска с каждой итерацией. То есть для достижения нужной сложности мы должны на каждой итерации сокращать круг поиска в каждом из массивов.
Рассмотрим следующую ситуацию: пусть у нас есть элемент <tex>a[i]</tex> из массива <tex>A</tex> и элемент <tex>b[j]</tex> из массива <tex>B</tex> и они связаны неравенством <tex>b[j </tex> {{- --}} <tex>1] < a[i] < b[j]</tex>. Тогда <tex>a[i]</tex> есть <tex>(j + i + 1)</tex>-ый порядковый элемент после слияния массивов. Это объясняется тем, что до <tex>a[i]</tex>-ого элемента идут <tex>(j </tex> {{- --}} <tex>1)</tex> элемент из массива <tex>B</tex>, <tex>i</tex> элементов из массива <tex>A</tex> (включая сам элемент <tex>a[i]</tex>). В итоге получаем <tex>(j </tex> {{--- }} <tex>1) + i + 2 = j + i + 1</tex>. Принимая это во внимание, будем выбирать <tex>i</tex> и <tex>j</tex> таким образом, чтобы <tex>j + i + 1 = k</tex>.
Подведем промежуточный итог:
# Инвариант <tex>j + i = k </tex> {{- --}} <tex>1</tex># Если <tex>b[j </tex> {{- --}} <tex>1] < a[i] < b[j]</tex>, то <tex>a[i]</tex> и есть <tex>k</tex>-ая порядковая статистика# Если <tex>a[i </tex> {{--- }} <tex>1] < b[j] < a[i]</tex>, то <tex>b[j]</tex> и есть <tex>k</tex>-ая порядковая статистика
Итак, если одно из двух последних условий выполняется, то мы нашли нужный элемент. Иначе нам нужно сократить область поиска, как задумывалось в начале.
Будем использовать <tex>i</tex> и <tex>j</tex> как опорные точки для разделения массивов. Заметим, что если <tex>a[i] < b[j]</tex>, то <tex>a[i] < b[j </tex> {{--- }} <tex>1]</tex> (иначе второе условие бы выполнялось). В таком случае на месте <tex>i</tex>-го элемента может стоять максимум <tex>i + (j </tex> {{- --}} <tex>2) + 2 = (i + j)</tex>-ый порядковый элемент после слияния массивов (так произойдет в случае, когда <tex>a[i] > b[j </tex> {{--- }} <tex>2]</tex>), а значит элемент с номером <tex>i</tex> и все до него в массиве <tex>A</tex> никогда не будут <tex>k</tex>-ой порядковой статистикой. Аналогично элемент с индексом <tex>j</tex> и все элементы, стоящие после него, в массиве <tex>B</tex> никогда не будут ответом, так как на позиции <tex>j</tex> будет стоять <tex>(i + j + 2)</tex>-ой порядковый элемент после слияния, порядковые номера остальных же будут еще больше. Таким образом, далее мы можем продолжать поиск в массиве <tex>A</tex> только в диапазоне индексов <tex>[i + 1, n </tex> {{- --}} <tex>1]</tex>, а в массиве <tex>B</tex> {{--- }} <tex>[0, j </tex> {{--- }} <tex>1]</tex>. Также, если <tex>b[j] < a[i]</tex>, то <tex>b[j] < a[i </tex> {{- --}} <tex>1]</tex>. Аналогичными рассуждениями приходим к тому, что в таком случае дальнейший поиск нужно осуществлять в массиве <tex>A</tex> в диапазоне <tex>[0, i </tex> {{--- }} <tex>1]</tex>, в массиве <tex>B</tex> {{- --}} <tex>[j + 1, m </tex> {{- --}} <tex>1]</tex>.
'''int''' findKthOrderStatistic('''int[]''' A, '''int''' n, '''int[]''' B, '''int''' m, '''int''' k):
'''int''' Bj_left = ((j == 0) ? INT_MIN : B[j-1])
'''int''' Bj = ((j == m) ? INT_MAX : B[j])
'''if''' (Bj_left < Ai && and Ai < Bj): '''return''' Ai '''else if''' (Ai_left < Bj && and Bj < Ai): '''return''' Bj
'''if''' (Ai < Bj):
'''else'''
==См. также==
