Поиск k-ой порядковой статистики в двух массивах
| Задача: |
| Пусть даны два отсортированных массива и размерами и соответственно. Требуется найти -ый порядковый элемент после их слияния. Будем считать, что все элементы в массивах различны и нумеруются с нуля. |
Содержание
Варианты решения
Наивное решение
Сольем два массива и просто возьмем элемент с индексом . Сливание будет выполнено за c использованием дополнительной памяти, что является существенным недостатком.
Чуть менее наивное решение
Будем использовать два указателя, с помощью которых сможем обойти массивы не сливая их. Поставим указатели на начало каждого из массивов. Будем увеличивать на единицу тот из них, который указывает на меньший элемент. После -ого добавления сравним элементы, на которых стоят указатели. Меньший из них и будет ответом. Таким образом, мы получим -ый элемент за шагов.
Еще одно решение
В первом массиве выберем серединный элемент и бинпоиском найдем во втором массиве позицию , на котором стоит наибольший элемент, меньший . Если , то мы нашли -ую порядковую статистику — это элемент . Иначе, если , то далее тем же способом ищем в массиве в диапазоне индексов , а если , то в диапазоне индексов . Решая задачу таким способом, мы получим асимптотику .
Совсем не наивное решение
Оба решения, приведенные выше, работают за линейное время, то есть приемлемы только при небольших значениях . Следующее решение работает за .
Чтобы получить логарифмическую сложность, будем использовать бинарный поиск, который сокращает область поиска с каждой итерацией. То есть для достижения нужной сложности мы должны на каждой итерации сокращать круг поиска в каждом из массивов.
Рассмотрим следующую ситуацию: пусть у нас есть элемент из массива и элемент из массива и они связаны неравенством . Тогда есть -ый порядковый элемент после слияния массивов. Это объясняется тем, что до -ого элемента идут элемент из массива , элементов из массива (включая сам элемент ). В итоге получаем . Принимая это во внимание, будем выбирать и таким образом, чтобы .
Подведем промежуточный итог:
- Инвариант
- Если , то и есть -ая порядковая статистика
- Если , то и есть -ая порядковая статистика
Итак, если одно из двух последних условий выполняется, то мы нашли нужный элемент. Иначе нам нужно сократить область поиска, как задумывалось в начале.
Будем использовать и как опорные точки для разделения массивов. Заметим, что если , то (иначе второе условие бы выполнялось). В таком случае на месте -го элемента может стоять максимум -ый порядковый элемент после слияния массивов (так произойдет в случае, когда ), а значит элемент с номером и все до него в массиве никогда не будут -ой порядковой статистикой. Аналогично элемент с индексом и все элементы, стоящие после него, в массиве никогда не будут ответом, так как на позиции будет стоять -ой порядковый элемент после слияния, порядковые номера остальных же будут еще больше. Таким образом, далее мы можем продолжать поиск в массиве только в диапазоне индексов , а в массиве — . По аналогии, если , то (иначе выполнялось бы третье условие). Аналогичными рассуждениями приходим к тому, что в таком случае дальнейший поиск нужно осуществлять в массиве в диапазоне , в массиве — .
Стоит отметить, что еще нам не нужно рассматривать элементы, стоящие и в том, и в другом массивах на позициях от -ой до конца (если такие есть), так как они тоже никогда не будут ответом. Поэтому первый раз запускаем нашу функцию от параметров .
int findKthOrderStatistic(int* A, int n, int* B, int m, int k):
if (n == 1):
if (B[k - 1] < A[0]):
return B[k - 1]
else if (A[0] < B[k - 2]):
return B[k - 2]
else
return A[0]
if (m == 1):
if (A[k - 1] < B[0]):
return A[k - 1]
else if (B[0] < A[k - 2]):
return A[k - 2]
else
return B[0]
int i = n / 2
int j = (k - 1) - i // j > 0, так как i <= (k / 2)
if (j >= m):
return findKthOrderStatistic(A + i + 1, n - i - 1, B, m, k - i - 1)
// чтобы сохранить инвариант, сделаем A[-1] = -INF и B[-1] = -INF
int Ai_left = ((i == 0) ? INT_MIN : A[i-1])
int Bj_left = ((j == 0) ? INT_MIN : B[j-1])
if (Bj_left < A[i] and A[i] < B[j]):
return A[i]
else if (Ai_left < B[j] and B[j] < A[i]):
return B[j]
if (A[i] < B[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)
Чтобы алгоритм работал за , будем передавать первым массивом в функцию тот, длина которого меньше. Тогда первый массив на каждой итерации уменьшается в два раза, как только его размер становится равным единице, за несколько сравнений мы находим ответ. Таким образом мы получаем заявленную асимптотику.
