Изменения

Перейти к: навигация, поиск
Совсем не наивное решение
Будем использовать <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>\mathtt{findKthOrderStatistic}(A, \min(n, k), B, \min(m, k), k)</tex>.
<tex>\mathtt{ '''int''' findKthOrderStatistic}</tex>('''int*''' A, '''int''' n, '''int*''' B, '''int''' m, '''int''' k):
'''int''' i = n / 2
'''int''' j = (k - 1) - i <font color=green>// j > 0, так как i <= (k / 2) </font>
577
правок

Навигация