3622
правки
Изменения
м
→Совсем не наивное решение
'''int''' findKthOrderStatistic('''int*''' A, '''int''' n, '''int*''' B, '''int''' m, '''int''' k):
'''if''' (n == 1):<font color=green>// в этом случае можно сразу дать ответ </font> '''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):<font color=green>// симметричен случаю с n = 1 </font>
'''return''' findKthOrderStatistic(B, m, A, n, k)
'''int''' i = n / 2
'''int''' j = (k - 1) - i <font color=green>// j > 0, так как i <= (k / 2) </font>
'''if''' (j >= m):
'''return''' findKthOrderStatistic(A + i + 1, n - i - 1, B, m, k - i - 1)
<font color=green>// чтобы сохранить инвариант, сделаем A[-1] = -INF и B[-1] = -INF </font>
'''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'''
