求两个有序数组中位数-python3.6

题目描述：Median of Two Sorted Arrays

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题目 Median of Two Sorted Arrays

方法1 直接遍历

直接的解法是遍历两个数组并计数，类似归并排序里面的有序数组的合并，复杂度为O（n）。代码如下：

 1 def getMedian(nums1, nums2, n):
 2 　　ans1, ans2 = -1, -1
 3 　　i = j = 0
 4 　　for count in range(n+1):
 5 　　　　if i < n and (nums1[i] < nums2[j] or j >= n):
 6 　　　　　　ans1 = ans2
 7 　　　　　　ans2 = nums1[i]
 8 　　　　　　i += 1
 9 　　　　else :
10 　　　　　　ans1 = ans2
11 　　　　　　ans2 = nums2[j]
12 　　　　　　j += 1
13 　　return (ans1 + ans2)/2.0
14 
15 if __name__ == '__main__':
16 　　nums1 = [1, 12, 15, 26, 38]
17 　　nums2 = [2, 13, 17, 30, 45]
18 　　n1 = len(nums1)
19 　　n2 = len(nums2)
20 　　if n1 == n2:
21 　　　　print("Median is %s", getMedian(nums1, nums2, n1))
22 　　else:
23 　　　　print("Can't work for nums of unequal size")

方法2 分治法

需要用分治法求解，时间复杂度为O(log (m+n))。

1.假设数组A的中位数为m1，数组B为m2，例如：nums1 = {1, 12, 15, 26, 38}， nums2 = {2, 13, 17, 30, 45}，m1 = 15 ，m2 = 17 。

2.由于m1<m2，则可以确定中位数即为下面两个子数组的中位数：[15, 26, 38] 和 [2, 13, 17]

3.重复步骤1、2，可以得到 m1 = 26， m2 = 13. 得到两个子数组：[15, 26] 和[13, 17]

4.这时，由于n=2，无法在继续分下去了。可以直接计算得：

median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
= (max(15, 13) + min(26, 17))/2
= (15 + 17)/2
= 16

代码如下：

 1  def median(nums, n):
 2 
 3 　　if n%2 == 0:
 4 　　　　return (nums[n//2] + nums[n//2-1])/2.0
 5 　　else:
 6 　　　　return nums[n//2]
 7 
 8 def getMedian(nums1, nums2, n):
 9 　　m1, m2 = -1, -1
10 　　if n <= 0:
11 　　　　return -1
12 　　elif n == 1:
13 　　　　return (nums1[0] + nums2[0]) / 2
14 　　elif n == 2:
15 　　　　return (max(nums1[0], nums2[0]) + min(nums1[1], nums2[1])) / 2
16 　　m1 = median(nums1, n)
17 　　m2 = median(nums2, n)
18 　　# /* 相等可直接返回 */
19 　　if m1 == m2:
20 　　　　return m1
21 　　if m1 < m2:
22 　　　　if n%2 == 0:
23 　　　　　　return getMedian(nums1[n//2-1:], nums2[:n//2+1], n//2 + 1)
24 　　　　else:
25 　　　　　　return getMedian(nums1[n//2:], nums2[:n//2+1], n//2 + 1)
26 　　else:
27 　　　　if n%2 == 0:
28 　　　　　　return getMedian(nums2[n//2-1:], nums1[:n//2+1], n//2 + 1)
29 　　　　else:
30 　　　　　　return getMedian(nums2[n//2:], nums1[:n//2+1], n//2 + 1)
31 
32 if __name__ == "__main__":
33 　　nums1 = [1, 12, 15, 26, 38]
34 　　nums2 = [2, 13, 17, 30, 45]
35 　　n1 = len(nums1)
36 　　n2 = len(nums2)
37 　　if n1 == n2:
38 　　　　print("Median is %s", getMedian(nums1, nums2, n1))
39 　　else:
40 　　　　print("Doesn't work for arrays of unequal size")