577
правок
Изменения
→Совсем не наивное решение
В первом массиве выберем серединный элемент <tex>(i = 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(n) + \logmin(n, m)))</tex>.
Чтобы получить логарифмическую сложность, будем использовать [[Целочисленный двоичный поиск|бинарный поиск]], который сокращает область поиска с каждой итерацией. То есть для достижения нужной сложности мы должны на каждой итерации сокращать круг поиска в каждом из массивов.
Стоит отметить, что еще нам не нужно рассматривать элементы, стоящие и в том, и в другом массивах на позициях от <tex>k</tex>-ой до конца (если такие есть), так как они тоже никогда не будут ответом. Поэтому первый раз запускаем нашу функцию от параметров <tex>\mathtt{findKthOrderStatistic}(A, \min(n, k), B, \min(m, k), k)</tex>.
'''int''' findKthOrderStatistic('''int*''' A, '''int''' n, '''int*''' B, '''int''' m, '''int''' k):
'''if''' (n == 1):
'''if''' (A[0] > B[k - 1]):
'''return''' B[k - 1]
'''else'''
'''return''' A[0]
'''if''' (m == 1):
'''if''' (B[0] > A[k - 1]):
'''return''' A[k - 1]
'''else'''
'''return''' B[0]
'''int''' i = n / 2
'''int''' j = (k - 1) - i <font color=green>// j > 0, так как i <= (k / 2) </font>
'''int''' Ai_left = ((i == 0) ? INT_MIN : A[i-1])
'''int''' Bj_left = ((j == 0) ? INT_MIN : B[j-1])
'''if''' (Bj_left < Ai A[i] and Ai A[i] < BjB[j]): '''return''' AiA[i] '''else if''' (Ai_left < Bj B[j] and Bj B[j] < AiA[i]): '''return''' BjB[j] '''if''' (Ai A[i] < BjB[j]):
'''return''' findKthOrderStatistic(A + i + 1, n - i - 1, B, j, k - i - 1)
'''else'''
'''return''' findKthOrderStatistic(A, i, B + j + 1, m - j - 1, k - j - 1)
==См. также==
