Изменения

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

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

127 байт добавлено, 11:05, 18 апреля 2015
Еще одно решение
=== Еще одно решение ===
В первом массиве выберем серединный элемент <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) * log(m))</tex>.
==См. также==
577
правок

Навигация