Поиск k-ой порядковой статистики в двух массивах — различия между версиями
(→Варианты решения) |
(→Варианты решения) |
||
Строка 40: | Строка 40: | ||
'''else''' | '''else''' | ||
'''return''' findKthOrderStatistic(A, i, B + j + 1, m - j - 1, k - j - 1) | '''return''' findKthOrderStatistic(A, i, B + j + 1, m - j - 1, k - j - 1) | ||
+ | |||
+ | == Ссылки == | ||
+ | * [http://articles.leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html Find the k-th Smallest Element in the Union of Two Sorted Arrays] |
Версия 22:14, 15 апреля 2015
Содержание
Постановка задачи
Пусть даны два отсортированных массива
и размерами и соответственно. Требуется найти -ый порядковый элемент после их слияния. Будем считать, что все элементы в массивах различны и нумеруются с нуля.Варианты решения
Наивное решение
Сольем два массива и просто возьмем элемент с индексом
. Сливание будет выполнено за .Чуть менее наивное решение
Будем использовать два указателя, с помощью которых сможем обойти массивы не сливая их. Поставим указатели на начало каждого из массивов. Будем увеличивать на единицу тот из них, который указывает на меньший элемент. После
-ого добавления сравним элементы, на которых стоят указатели. Меньший из них и будет ответом. Таким образом, мы получим -ый элемент за шагов.Совсем не наивное решение
Оба решения, приведенные выше, работают за линейное время, то есть приемлемы только при небольших значениях
. Следующее решение работает за .Чтобы получить логарифмическую сложность, будем использовать бинарный поиск, который сокращает область поиска с каждой итерацией. То есть для достижения нужной сложности мы должны на каждой итерации сокращать круг поиска в каждом из массивов.
Рассмотрим следующую ситуацию: пусть у нас есть элемент
из массива и элемент из массива и они связаны неравенством . Тогда есть -ый порядковый элемент после слияния массивов. Это объясняется тем, что до -ого элемента идут элемент из массива , элементов из массива (включая сам элемент ) и так как индексация массивов начинается с нуля, то необходимо прибавить еще . В итоге получаем . Принимая это во внимание, будем выбирать и таким образом, чтобы .Подведем промежуточный итог:
- Инвариант
- Если , то и есть -ая порядковая статистика
- Если , то и есть -ая порядковая статистика
Итак, если одно из двух последних условий выполняется, то мы нашли нужный элемент. Иначе нам нужно сократить область поиска, как задумывалось в начале.
Будем использовать
и как опорные точки для разделения массивов. Заметим, что если , то (иначе второе условие бы выполнялось). В таком случае на месте -го элемента может стоять максимум -ый порядковый элемент после слияния массивов (так произойдет в случае, когда ), а значит элемент с номером и все до него в массиве никогда не будут -ой порядковой статистикой. Аналогично элемент с индексом и все элементы, стоящие после него, в массиве никогда не будут ответом, так как на позиции будет стоять -ой порядковый элемент после слияния, порядковые номера остальных же будут еще больше. Таким образом, далее мы можем продолжать поиск в массиве только в диапазоне индексов , а в массиве - . Также, если , то . Аналогичными рассуждениями приходим к тому, что в таком случае дальнейший поиск нужно осуществлять в массиве в диапазоне , в массиве - .int findKthOrderStatistic(int[] A, int n, int[] B, int m, int k): int i = random(0 .. n - 1) int j = (k - 1) - i // чтобы сохранить инвариант сделаем A[-1] = -INF и A[n] = +INF B[-1] = -INF и B[m] = +INF int Ai_left = ((i == 0) ? INT_MIN : A[i-1]) int Ai = ((i == n) ? INT_MAX : A[i]) int Bj_left = ((j == 0) ? INT_MIN : B[j-1]) int Bj = ((j == m) ? INT_MAX : B[j]) if (Bj_left < Ai && Ai < Bj): return Ai else if (Ai_left < Bj && Bj < Ai): return Bj if (Ai < Bj): 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)