求两个有序数组的中位数,要求时间复杂度log(m+n)

求两个有序数组的中位数

第一种方法

思路：中位数的求法，将两个列表排成一个有序的数组，当排到两个列表长度和的一半的时候即可终止循环找出中位数
时间复杂度：O(log(m+n))
def midd_num(l1,l2):
index = 0
l1_index = 0
l2_index = 0
lst_tmp = []
l1_len = len(l1)
l2_len = len(l2)
length = (l1_len+l2_len)//2
if l1_len == l2_len == 0: #当两个列表为空的时候
raise ValueError
if length == 0: #当有一个列表为空的时候
return (l1+l2)[0]
while index <= length:
if l1_index >= l1_len: #即l1列表里面的元素全部加到lst_tmp
lst_tmp = lst_tmp+l2[l2_index:]
break
elif l2_index >= l2_len: #即l2列表里面的元素全部加到lst_tmp
lst_tmp = lst_tmp+l1[l1_index:]
break
elif l1[l1_index] > l2[l2_index]: #l1元素大于l2元素时
lst_tmp.append(l2[l2_index])
l2_index += 1
index += 1
elif l1[l1_index] lst_tmp.append(l1[l1_index])
l1_index+= 1
index += 1
elif l1[l1_index] == l2[l2_index]: #l1元素与l2元素相等时
lst_tmp.append(l1[l1_index])
lst_tmp.append(l2[l2_index])
l1_index+= 1
l2_index+= 1
index += 2
if (l1_len+l2_len) % 2 == 0: #元素个数为偶数
return (lst_tmp[length] +lst_tmp[length-1])/2
else:
return lst_tmp[length]
lst1=[12,25,232,54]
lst2= [1,10]
print(midd_num(lst1, lst2))


第二种方法

思路：通过函数堆模块里面的merge方法返回一个有序的迭代器，循环取值加入到新的列表之中，再判断列表元素奇偶的个数，求出中位数
时间复杂度：O(log(m+n))
import heapq
def mid_num(lst_1, lst_2):
length = (len(lst_1) + len(lst_2))//2
index = 0
lst_tmp = []
for i in heapq.merge(lst_1,lst_2):
if index <= length:
lst_tmp.append(i)
if (index == length):
if (len(lst_1) + len(lst_2))%2:
return lst_tmp[length]
else:
return (lst_tmp[length-1] +lst_tmp[length])/2
index += 1
lst_tmp = lst1 + lst2
return lst_tmp[0]
lst1=[2,3,5]
lst2= []
print(mid_num(lst1, lst2))