577
правок
Изменения
Нет описания правки
Будем использовать два указателя, с помощью которых сможем обойти массивы не сливая их. Поставим указатели на начало каждого из массивов. Будем увеличивать на единицу тот из них, который указывает на меньший элемент. После <tex>(k - 1)</tex>-ого добавления сравним элементы, на которых стоят указатели. Меньший из них и будет ответом. Таким образом, мы получим <tex>k</tex>-ый элемент за <tex>O(k)</tex> шагов.
=== Совсем не наивное решение ===
Оба решения, приведенные выше, работают за линейное время, то есть приемлемы только при небольших значениях <tex>k</tex>. Следующее решение работает за <tex>O(\log(n) + \log(m))</tex>.
Чтобы получить логарифмическую сложность, будем использовать [[Целочисленный двоичный поиск|бинарный поиск]], который сокращает область поиска с каждой итерацией. То есть для достижения нужной сложности мы должны на каждой итерации сокращать круг поиска в каждом из массивов.
'''return''' findKthOrderStatistic(A, i, B + j + 1, m - j - 1, k - j - 1)
Таким образом первый массив на каждой итерации уменьшается в два раза, как только он становится маленьким (это произойдет за <tex>O(\log(n))</tex> операций), мы запустим бинпоиск и найдем ответ за <tex>O(log\og(m))</tex>. Итоговая асимптотика {{---}} <tex>O(\log(n) + \log(m))</tex>.
=== Еще одно решение ===
В первом массиве выберем серединный элемент <tex>(i = n / 2)</tex> и бинпоиском найдем во втором массиве позицию <tex>j</tex>, на которой должен стоять (или стоит) элемент <tex>(a[i] - 1)</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>.
==См. также==
* [[Поиск k-ой порядковой статистики за линейное время|Поиск k-ой порядковой статистики за линейное время]]
== Источники информации ==
* [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]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
[[Категория: Другие сортировки]]
