两个有序数组的中位数

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)).

Example 1:nums1 = [1, 3] nums2 = [2]

The median is 2.0

Example 2:nums1 = [1, 2] nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

这个是 leetcode 的第三题，看到这道题首先想到的就是 MergeSort 中的 Merge，可以用一个大小等于两个数组之和的数组储存，然后二分搜索即可。但是这样太废空间，所以又想了另外一个办法，因为已知数组长度，用两个整数代表数组之和的中间位置，如果是数组之和是奇数，则两个整数相等即可。还需要一个 flag 来表示当前元素所属数组，这样如果发现中位数则存储之，存满两个（可能是一个位置）直接返回他们的平均数即可，解法就不贴了，解体过程中注意考虑空数组的情况，然后多想象 merge 操作如何处理数组，debug时可以打印 flag，中位数索引，中位数值。