Изменения

Перейти к: навигация, поиск

Поиск k-ой порядковой статистики в двух массивах

14 байт добавлено, 23:45, 18 апреля 2015
м
Совсем не наивное решение
'''return''' findKthOrderStatistic(A, i, B + j + 1, m - j - 1, k - j - 1)
Чтобы алгоритм работал за <tex>O(\log(\min(n, m)))</tex>, будем передавать первым массивом в функцию тот, длина которого меньше. Тогда длина рассматриваемой области первого массива на каждой итерации уменьшается в два раза. Как только После того, как она станет равна единице, то ответ можно будет получить за несколько сравнений легко получить ответ.
==См. также==

Навигация