Цитата: Alone Coder от декабря 12, 2011, 16:30Все-таки медианы обоих массивов не могут быть больше медианы общего массива. Вы наверное забыли про отсортированность.
Если середина первого массива меньше, чем середина второго, то это вовсе не значит, что она меньше медианы.
Цитата: Alone Coder от декабря 12, 2011, 16:30Пример можете привести, где это не так? Под серединой вы тут медиану имеете в виду? Напоминаю: массивы отсортированы.
Если середина первого массива меньше, чем середина второго, то это вовсе не значит, что она меньше медианы.
Цитата: RawonaM от декабря 12, 2011, 12:03Если середина первого массива меньше, чем середина второго, то это вовсе не значит, что она меньше медианы.
Что скажете, будет ли всегда работать?
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)
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)
Страница создана за 0.035 сек. Запросов: 20.