def merge(lst1, lst2):
if not lst1:
return [lst2[idx] for idx in range(len(lst2)-1, -1, -1)] # lst2[::-1]
if not lst2:
return [lst1[idx] for idx in range(len(lst1)-1, -1, -1)] # lst1[::-1]
merged_lst = []
i,j = len(lst1)-1 ,len(lst2)-1
while i > -1 and j > -1:
if lst1[i] > lst2[j]:
merged_lst.append(lst1[i])
i -=1
elif lst1[i] < lst2[j]:
merged_lst.append(lst2[j])
j -=1
else:
merged_lst.extend( [lst1[i],lst2[j]] )
i -=1
j -=1
if i > -1:
merged_lst.extend( lst1[idx] for idx in range(i,-1,-1))
# or merged_lst.extend( lst1[:i+1][::-1])
else:
merged_lst.extend( lst2[idx] for idx in range(j,-1,-1))
# or merged_lst.extend( lst2[:j+1][::-1])
return merged_lst
объяснение :
вспомогательные функции
def reverse_lst( lst):
return [lst[idx] for idx in range(len(lst)-1, -1, -1)]
# if you don't even want to use list comprehension
def basic_reverse_lst( lst):
rev_lst = []
# start( inclusive), stop( exclusive), step
for idx in range(len(lst)-1 , -1, -1):
rev_lst.append( lst[idx])
return rev_lst
функция слияния
def merge(lst1, lst2):
# assuming lst1 and lst2 are sorted list(ascending order)
регистр пустого списка (я расскажу об этом позже)
if not lst1:
# since lst1 is empty our merge list will only contain elements of lst2
return basic_reverse_lst(lst2) # if you don't want to use lst2[::-1] and list comprehension
if not lst2:
return reverse_lst(lst1)
Функция merged_lst в конечном итоге будет возвращена функцией слияния, которая будет содержать наш окончательный ответ (в порядке убывания))
merged_lst = []
i и j инициализируются с последним индексом lst1 и lst2 соответственно, потому что мы будем обходить список в обратном порядкето есть от самого большого элемента списка к наименьшему.
# last_idx = len(lst) -1
i,j = len(lst1)-1 ,len(lst2)-1
Понимание того, как i и j уменьшаются, имеет решающее значение
Представьте две стрелки, одна из которых указывает на элемент с индексом ilst1 и другой элемент с индексом j в lst2 продолжают перемещать эти стрелки по мере изменения значений i и j.
выполняется пока цикл до тех пор, пока один из списка не будет исчерпан, т.е. пока мы не пройдем хотя бы один изсписок полностью, который подразумевает, что через некоторое времястрелка будет указывать на элемент с индексом 0, и в конце она будет указывать на -1 (в python это последний элемент списка, но мы рассматриваем его как индекс вне связанной ситуации или здесь просто это означает, что мы полностью перешлиэтот список).
while i > -1 and j > -1:
if lst1[i] > lst2[j]:
merged_lst.append(lst1[i])
i -=1
elif lst1[i] < lst2[j]:
merged_lst.append(lst2[j])
j -=1
else:
merged_lst.extend( [lst1[i],lst2[j]] )
i -=1
j -=1
'''
# you can use extend( some_sequence) or do append()
# here it depends what you want since you have not mentioned in your question exactly
# what kind of behaviour you want when elements of two list are same I presumed that you want to add both of them in merged list
merged_lst.append(lst1[i])
merged_lst.append(lst2[j])
'''
извлечение остальных элементов в обратном порядке из списка, через который мы еще не полностью прошли, это становится точно таким же, как наш стартовый случай, когда один из списка передается нашему слиянию функций (lst1, lst2)был пуст, поэтому все, что нам нужно сделать, это перевернуть непустой список (тот, который мы еще не полностью просмотрели).
if i > -1:
# lst1 is not completely traversed yet
# merged_lst.extend( lst1[idx] for idx in range(i,-1,-1)) or # lst1[:i+1][::-1]
rest = lst1[:i+1] # rest contains elements of lst1 which we have not seen in while loop
merged_lst.extend( reverse_lst(rest))
else:
# lst2 is not completely traversed yet
# you can extract then reverse like we are doing in above if condition or you can simply do it in one line
merged_lst.extend( lst2[idx] for idx in range(j,-1,-1)) # or lst2[:j+1][::-1]
return merged_lst
print(merge([1,2,23,42],[])) # [42, 23, 2, 1]
print(merge([1,2,23,42], [5,7,11,19,21])) # [42, 23, 21, 19, 11, 7, 5, 2, 1]
print(merge([1,21,23,42], [5,7,11,19,21,97])) # [97, 42, 23, 21, 21, 19, 11, 7, 5, 1]
print(merge([1,19,19,21,21,23,42], [5,7,11,19,21,21,97])) # [97, 42, 23, 21, 21, 21, 21, 19, 19, 19, 11, 7, 5, 1]