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