Даны два массива чисел X[1..n] и Y[1..n], оба сортированные.
Нужно дать алгоритм со сложностью O(lg n) находящий медиану всех 2n чисел из обоих массивов.
Мое решение основывается на том, что медиана двух массивов находится между медианами каждого массива по отдельности, т.е. если m - это медиана всех чисел, то X[n/2]<m<=Y[n/2] или Y[n/2]<m<=X[n/2]. Доказательство: если X[n/2]<m и Y[n/2]<m, то количество чисел меньших или равных m из обоих массивов превышает 2n/2, поэтому m не может быть медианой. Аналогично если обе медианы больше m.
Прим.: под медианой понимается нижняя медиана, а деление всегда без остатка.
Поэтому можно предложить такой алгоритм (псевдокод):
Find-M(A,p,r,B,s,t)
if r-p == 0
return min(A[p],B)
m1 = A[(r+p)/2]
m2 = B[(t+s)/2]
if m1 >= m2
return Find-M(A,p,(r+p)/2,B,(t+s+1)/2,t)
else
return Find-M(A,(r+p+1)/2,r,B,s,(t+s)/2)
Что скажете, есть ли тут ошибки?
Что такое r,p,s,t?
Начало и конец (под)массива, который функция получает.
Изначальный вызов будет Find-M(X,1,n,Y,1,n).
Не, что-то не клеится. Надо исправлять.
Кажется допилил. Исправил в изначальном сообщении. Вот код на пюфоне:
def FindM(A,p,r,B,s,t):
print A[p:r+1]
print B[s:t+1]
print '---'
if (r == p):
return min(A[p],B[s])
m1 = A[(r+p)/2]
m2 = B[(t+s)/2]
if (m1 >= m2):
return FindM(A,p,(r+p)/2,B,(t+s+1)/2,t)
else:
return FindM(A,(r+p+1)/2,r,B,s,(t+s)/2)
X = ['',1,4,5,7]
Y = ['',3,6,9,10]
print FindM(X,1,len(X)-1,Y,1,len(Y)-1)
Что скажете, будет ли всегда работать?
Еще есть задачка как обобщение этому случаю: нужно написать алгоритм, который находит k-ное значение по возрастанию из таких же двух массивов. Cложность алгоритма должна быть O(lg min(k,2n-k)).
Можно решать в лоб, но раз уже есть Find-M, то берем и делаем так:
def FindK(k,A,p,r,B,s,t):
n = (r-p)+1 # the length of A or B
if k <= n:
# leave only the first k elements in each array,
# now the k-th element of the old arrays is the median of the new arrays
return FindM(A,p,p+k-1,B,s,s+k-1)
else:
# leave only the last k elements in each array, again the k-th element
# of the old arrays is the is the upper median of the new ones
return FindUM(A,r-(2*n-k)+1,r,B,t-(2*n-k)+1,t)
Верхняя медиана соответственно:
def FindUM(A,p,r,B,s,t):
if (r == p):
return max(A[p],B[s])
m1 = A[(r+p+1)/2]
m2 = B[(t+s+1)/2]
if (m1 >= m2):
return FindUM(A,p,(r+p)/2,B,(t+s+1)/2,t)
else:
return FindUM(A,(r+p+1)/2,r,B,s,(t+s)/2)
Как вам?
Меня что смущает. Я нашел ответы к книге, а там в ответах алгоритм нахождения медианы намного-намного запутаннее... Не могу сказать, что такого не случается, но прямо такая разница чтобы...
Потом выложу алгоритм из ответов.
Цитата: RawonaM от декабря 12, 2011, 12:03
Что скажете, будет ли всегда работать?
Если середина первого массива меньше, чем середина второго, то это вовсе не значит, что она меньше медианы.
Я вообще не представляю, как тут возможно логарифмическое время.
По идее надо начать со сравнения k-го элемента первого массива с 1-м элементом второго массива. Вопрос, какое оптимальное k. Дальше - хуже.
Цитата: Alone Coder от декабря 12, 2011, 16:30
Если середина первого массива меньше, чем середина второго, то это вовсе не значит, что она меньше медианы.
Пример можете привести, где это не так? Под серединой вы тут медиану имеете в виду? Напоминаю: массивы отсортированы.
Цитата: Alone Coder от декабря 12, 2011, 16:30
Если середина первого массива меньше, чем середина второго, то это вовсе не значит, что она меньше медианы.
Все-таки медианы обоих массивов не могут быть больше медианы общего массива. Вы наверное забыли про отсортированность.
Действительно.
А в книге ответ на вопрос про нахождение медианы вот такой: