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:

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

The median is 2.0

Example:

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

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

算法思路

主要是使用了分治的思想，想法和上一道题目Reverse Pairs 差不多。 1. 题目要我求两个已经排列好的序列A与B的中位数，两个序列的长度分别是m与n，既求两个序列中第k=（m+n）2$k = /frac{（m + n）}{2}$个数。 2. 我们假设p和q分别是A和B的中位数（这个很容易求），然后比较p和q的大小，若p < q，说明A中P之前的数字都不是两个序列的中位数。我们就可以A面半部分的数字“抛弃”掉。现在的问题就变成了求剩下的数字中第k−p$k - p$个数字了。 3. 我们通过这样每次都扔掉其中一个序列的一半的数字，最后就可以很快得求得问题的解。 4. 我们要注意几个边界问题。（1）如果A或者B为空，只需返回A[k−1]$A[k - 1]$或者B[k−1]$B[k- 1]$。（2）如果k为1，则返回A[0]$A[0]$与B[0]$B[0]$中比较小的那个数。（3）如果A[k/2−1]=B[k/2−1]$A[k/2-1]=B[k/2-1]$，则随便返回其中一个。

算法代码