Изменения

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

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

2 байта добавлено, 14:39, 18 апреля 2015
Нет описания правки
Будем использовать <tex>i</tex> и <tex>j</tex> как опорные точки для разделения массивов. Заметим, что если <tex>a[i] < b[j]</tex>, то <tex>a[i] < b[j - 1]</tex> (иначе второе условие бы выполнялось). В таком случае на месте <tex>i</tex>-го элемента может стоять максимум <tex>i + (j - 2) + 2 = (i + j)</tex>-ый порядковый элемент после слияния массивов (так произойдет в случае, когда <tex>a[i] > b[j - 2]</tex>), а значит элемент с номером <tex>i</tex> и все до него в массиве <tex>A</tex> никогда не будут <tex>k</tex>-ой порядковой статистикой. Аналогично элемент с индексом <tex>j</tex> и все элементы, стоящие после него, в массиве <tex>B</tex> никогда не будут ответом, так как на позиции <tex>j</tex> будет стоять <tex>(i + j + 2)</tex>-ой порядковый элемент после слияния, порядковые номера остальных же будут еще больше. Таким образом, далее мы можем продолжать поиск в массиве <tex>A</tex> только в диапазоне индексов <tex>[i + 1, n - 1]</tex>, а в массиве <tex>B</tex> {{---}} <tex>[0, j - 1]</tex>. По аналогии, если <tex>b[j] < a[i]</tex>, то <tex>b[j] < a[i - 1]</tex> (иначе выполнялось бы третье условие). Аналогичными рассуждениями приходим к тому, что в таком случае дальнейший поиск нужно осуществлять в массиве <tex>A</tex> в диапазоне <tex>[0, i - 1]</tex>, в массиве <tex>B</tex> {{---}} <tex>[j + 1, m - 1]</tex>.
Стоит отметить, что еще нам не нужно рассматривать элементы, стоящие и в том, и в другом массивах на позициях от <tex>k</tex>-ой до конца (если такие есть), так как они тоже никогда не будут ответом. Поэтому первый раз запускаем нашу функцию от параметров <tex>findKthOrderStatistic(A, \min(n, k - 1), B, \min(m, k - 1), k)</tex>.
<font color=green>// во избежание коллизий перед вызовом функции проинициализируем A[n] = +INF, B[m] = +INF </font>
577
правок

Навигация