Изменения

|definition = Пусть даны Даны два отсортированных массива <tex>Aa</tex> и <tex>Bb</tex> размерами <tex>n</tex> и <tex>m</tex> соответственно. Требуется [[Поиск k-ой порядковой статистики|найти <tex>k</tex>-ый порядковый элемент]] после их слияния. Будем считать, что все элементы в массивах различны и нумеруются с нуля.}}

Сольем два массива и просто возьмем элемент с индексом <tex>k- 1</tex> {{---}} . Слияние будет выполнено за время <tex>1O(n + m)</tex>. Сливание будет выполнено за , к тому же этот алгоритм использует <tex>O(n + m)</tex> c использованием дополнительной памяти, что является существенным недостатком. 

Будем использовать два указателя, с помощью которых сможем обойти массивы , не сливая их. Поставим указатели на начало каждого из массивов. Будем увеличивать на единицу тот из них, который указывает на меньший элемент. После <tex>(k</tex> {{---}} <tex>1)</tex>-ого добавления ой итерации сравним элементы, на которых стоят указатели. Меньший из них и будет ответом. Таким образом, мы получим <tex>k</tex>-ый элемент за <tex>O(k)</tex> шагов. === Еще одно решение ===В первом массиве выберем элемент c индексом <tex>i = \dfrac{n}{2}</tex> и [[Целочисленный двоичный поиск|бинарным поиском]] найдем во втором массиве позицию <tex>j</tex>, на которой стоит наибольший элемент, меньший <tex>a[i]</tex>. Если <tex>i + j = k - 2</tex>, то мы нашли <tex>k</tex>-ую порядковую статистику {{---}} это элемент <tex>a[i]</tex>. Иначе, если <tex>i + j > k - 2</tex>, то далее тем же способом ищем в массиве <tex>a</tex> в диапазоне индексов <tex>[0, i - 1]</tex>, а если <tex>i + j < k - 2</tex>, то в диапазоне индексов <tex>[i + 1, n - 1]</tex>. Решая задачу таким способом, мы получим асимптотику <tex>O(\log(n) \cdot \log(m))</tex>. 

Оба решенияПриведём теперь решение, приведенные выше, работают работающее за линейное время, то есть приемлемы только при небольших значениях <tex>k</tex>. Следующее решение работает за <tex>O(\log(\min(n, m) + log(m))</tex>.

Чтобы получить логарифмическую сложность, будем использовать [[Целочисленный двоичный поиск|бинарный поиск]], который сокращает область поиска с каждой итерацией. То есть для достижения нужной сложности мы должны на каждой итерации сокращать круг поиска в каждом из массивов. Рассмотрим Для начала рассмотрим следующую ситуацию: пусть у нас есть элемент <tex>a[i]</tex> из массива <tex>Aa</tex> и элемент <tex>b[j]</tex> из массива <tex>Bb</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>Bb</tex>, <tex>(i+1)</tex> элементов из массива <tex>Aa</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>Aa</tex> никогда не будут <tex>k</tex>-ой порядковой статистикой. Аналогично элемент с индексом <tex>j</tex> и все элементы, стоящие после него, в массиве <tex>Bb</tex> никогда не будут ответом, так как после слияния на позиции <tex>j</tex> будет стоять <tex>(i + j + 2)</tex>-ой порядковый элемент после слияния, порядковые номера остальных же будут еще больше. Таким образом, далее мы можем продолжать поиск в массиве <tex>Aa</tex> только в диапазоне индексов <tex>[i + 1, n</tex> {{---}} <tex>1]</tex>, а в массиве <tex>Bb</tex> {{---}} <tex>[0, j</tex> {{---}} <tex>1]</tex>. ТакжеПо аналогии, если <tex>b[j] < a[i]</tex>, то <tex>b[j] < a[i</tex> {{---}} <tex>1]</tex>(иначе выполнялось бы третье условие). Аналогичными рассуждениями приходим к тому, что в таком случае дальнейший поиск нужно осуществлять в массиве <tex>Aa</tex> в диапазоне <tex>[0, i</tex> {{---}} <tex>1]</tex>, в массиве <tex>Bb</tex> {{---}} <tex>[j + 1, m</tex> {{---}} <tex>1]</tex>.  Стоит отметить, что еще нам не нужно рассматривать элементы, стоящие и в том, и в другом массивах на позициях от <tex>k</tex>-ой до конца (если такие есть), так как они тоже никогда не будут ответом. Поэтому первый раз запускаем нашу функцию от параметров <tex>findKthOrderStatistic(A, min(n, k - 1), B, min(m, k - 1), k)</tex>.

Стоит отметить, что нам не нужно рассматривать элементы, стоящие и в том, и в другом массивах на позициях от <font color=greentex>k<// во избежание коллизий перед вызовом функции проинициализируем A[tex>-ой до конца (если такие есть), так как они тоже никогда не будут ответом. Поэтому первый раз запускаем нашу функцию от параметров <tex>\mathtt{findKthOrderStatistic}(a, \min(n] = +INF, B[k), b, \min(m] = +INF , k), k)</fonttex>. '''int''' findKthOrderStatistic('''int*''' Aa, '''int''' n, '''int*''' Bb, '''int''' m, '''int''' k): '''if''' (n == 1): '''int''' tmp = binSearch(B, m, A[0]) <font color=green>// вернет позицию, на которой должен стоять элемент A[0] в массиве Bэтом случае можно сразу дать ответ </font> '''if''' (tmp > b[k):- 1] < a[0] '''return''' Bb[k - 1] '''else if''' (tmp == a[0] < b[k):- 2] '''return''' Ab[0k - 2]

'''return''' Ba[0] '''if''' m == 1 <font color=green>// симметричен случаю с n = 1 </font> '''return''' findKthOrderStatistic(b, m, a, n, k - 2] )

'''if''' (j >= m): '''return''' findKthOrderStatistic(A a + i + 1, n - i - 1, Bb, m, k- i - 1) <font color=green>// чтобы сохранить инвариант, сделаем Aa[-1] = -INF и Bb[-1] = -INF </font> '''int''' Ai_left aiLeft = ((i == 0) ? INT_MIN : Aa[i-1]) '''int''' Bj_left bjLeft = ((j == 0) ? INT_MIN : Bb[j-1]) '''if''' (Bj_left bjLeft < Ai a[i] '''and Ai ''' a[i] < Bj):b[j] '''return''' Aia[i] '''else if''' (Ai_left aiLeft < Bj b[j] '''and Bj ''' b[j] < Ai):a[i] '''return''' Bjb[j] '''if''' (Ai a[i] < Bj):b[j] '''return''' findKthOrderStatistic(A a + i + 1, n - i - 1, Bb, j, k - i - 1)

'''return''' findKthOrderStatistic(Aa, i, B b + j + 1, m - j - 1, k - j - 1)

Таким образом первый массив на каждой итерации уменьшается в два раза, как только он становится маленьким (это произойдет Чтобы алгоритм работал за <tex>O(\log(\min(n, m)))</tex> операций), мы запустим бинпоиск и найдем будем передавать первым массивом в функцию тот, длина которого меньше. Тогда длина рассматриваемой области первого массива на каждой итерации уменьшается в два раза. После того, как она станет равна единице, ответ можно будет получить за <tex>O(log(m))</tex>. Итоговая асимптотика - <tex>O(log(n) + log(m))</tex>несколько сравнений.

* [http://articles.leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html LeetCode {{---}} Find the k-th Smallest Element in the Union of Two Sorted Arrays]* [http://dcsobral.blogspot.ru/2011/05/cute-algorithm.html Blogspot {{---}} A Cute Algorithm]