【LeetCode with Python】 4. Median of Two Sorted Arrays
题目
原题页面:https://leetcode.com/problems/median-of-two-sorted-arrays/
本文地址:http://leetcode.xnerv.wang/median-of-two-sorted-arrays/
题目类型:Divide and Conquer, Array, Binary Search
难度评价:Hard
There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
分析
找两个有序数列的“中位值”。发现LeetCode上还是有不少坑。如,这个题目说的有序数列其实是从小到大排列的,不需要我们像处理其它经常埋坑的题那样“以小人之心度君子之腹”地去先检查A和B是从小到大还是从大到小,甚至有可能A从小到大而B却从大到小。其次,这个“median”并不是指“中位数”,而是“中位值”,两者的区别是:当m+n为奇数时,这两个词是一个概念。而当m+n为偶数时,中位数可以指按大小排在最中间的那两个数,而中位值则是指这两个数的平均数。何其坑哉!
代码
class Solution:
# @return a float
def findMedianSortedArrays(self, A, B):
len_a = len(A)
len_b = len(B)
len_total = len_a + len_b
if 0 == len_total:
return ''
if 0 == len_a and 1 == len_b:
return B[0]
if 1 == len_a and 0 == len_b:
return A[0]
if 1 == len_a and 1 == len_b:
return float(A[0] + B[0]) / 2
median_index = len_total / 2
is_odd = (1 == len_total % 2)
index_a = -1
index_b = -1
median_num = 0
for i in range(0, median_index + 1):
if index_a + 1 < len_a and (index_b + 1 >= len_b or A[index_a + 1] <= B[index_b + 1]):
index_a += 1
last_median_num = median_num
median_num = A[index_a]
else:
index_b += 1
last_median_num = median_num
median_num = B[index_b]
if is_odd:
median_num = median_num
else:
median_num = float(last_median_num + median_num) / 2
return median_num