# O(log(m+n)) in Python

• ``````def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
m_len, n_len, i, j = len(nums1), len(nums2), 0, 0
# 似乎可以不用判断
if m_len + n_len == 0: raise ValueError
# midian代表中间第几个是中间数，flag表示本次样例时是否是偶数个，因为偶数个的时候还要加上midian之前的数
# 比如num = [1, 2, 3, 4]  此时midian是 2，返回的结果应该是float(num[midian] + num[midian-1]) / 2
# midian represents the index half of the two list, flag represents the count of the two list is even
midian, flag = (m_len + n_len) >> 1, (m_len + n_len + 1) % 2
# 表示前一个数，免得在后面还要计算一次，直接在遍历的时候记录下来
# record the number before midian, avoid calculating again
midian_front_num = 0
while i < m_len and j < n_len:
# 找到中间数了
# Perfect! The midian is found
if i + j == midian:
midian_num = min(nums1[i], nums2[j])
# 这里要注意是不是奇数个
# Be careful! Is the count of two list even?
if flag: return float(midian_num + midian_front_num) / 2.0
else: return midian_num
# 让增加的始终保持是nums1, 方便返回结果
# to keep nums1 represents index increased
if nums1[i] < nums2[j]:
i, j, nums1, nums2, m_len, n_len, midian_front_num = i + 1, j, nums1, nums2, m_len, n_len, nums1[i]
else:
#
i, j, nums1, nums2, m_len, n_len, midian_front_num = j + 1, i, nums2, nums1, n_len, m_len, nums2[j]
# 到这肯定是没找到的
# Unforunately, we failed to find after executing the code above
# 把还有多余数的list放到nums1中，我比较讨厌做很多判断，这样就可以减少判断。
# put the reset data in nums1, to decrease judgements
if j < n_len: i, j, nums1, nums2, m_len, n_len = j, i, nums2, nums1, n_len, m_len
# 同上
# the same as above
if flag:
# 如果恰好i+j == midian，如果恰好又是偶数个的话，
if i+j == midian:
midian_front_num = nums2[n_len-1]
# 再恰好是i是0的话，你就掉到坑里去了
if i == 0:
midian_front_num = max(nums1[midian-j-1], midian_front_num)
# 这里之前没有加float，=。= 在[1, 2], [3, 4]的样例中，本机运行的2.5  oj运行的是2  不知道为什么没有转换成浮点数
# 上面的坑没有掉进去，这里掉进去了
# you should convert the result to float
return float(nums1[midian-j] + midian_front_num) / 2.0
else:
return float(nums1[midian-j] + nums1[midian-j-1]) / 2.0
# 这次是真的没坑了
return nums1[midian-j]
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.