Description
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
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
Discussion
首先题目已经规定了时间复杂度为O(log(m + n))，这就要求我们不能使用简单的合并排序再取中间值的方法，这样做的时间复杂度为O(m + n)。
实际上，我们可以采用类似于合并排序的方法来查找两个有序列表中第k小的元素。我们可以设置一个计数器，记录当前已经找到第m大的元素了。同时我们使用两个指针pA和pB，分别指向数组A和B的第一个元素。使用类似于merge sort的原理，如果数组A当前元素小，那么pA++，同时m++。如果数组B当前元素小，那么pB++，同时m++。最终当m等于k的时候，就得到了我们的答案。这样时间复杂度为O(k)。
这种方法下，每次剔除1个数。那么能不能每次剔除k/2个数呢。假设数组A和B数据个数都比k大。那么我们比较A和B中第k/2大的两个数，即A[k/2 - 1]和B[k/2 - 1]。为了简单，我们先假设k为偶数。如果A[k/2 - 1] < B[k/2 - 1]， 那么A[0]到A[k/2 - 1]之间的数都属于比第k大的数小的，可以直接剔除。使用这种办法，第1次可以剔除k/2个数，第2次可以剔除k/4个数……
算法的时间复杂度为O(n)。
C++ Code
double findKthSortedArrays(vector<int> & nums1, int base1, int len1, vector<int> & nums2, int base2, int len2, int k)
{
//假设数组1的长度比数组2短。否则下面计算的p1,p2之和可能不为k/2。
if(len1 > len2)
{
return findKthSortedArrays(nums2, base2, len2, nums1, base1, len1, k);
}
//若其中一个数组为空
if(len1 == 0)
{
return nums2[base2 + k - 1];
}
if(len2 == 0)
{
return nums1[base1 + k - 1];
}
if(k == 1)
{
return min(nums1[base1], nums2[base2]);
}
//每次去掉一半
int p1 = min(len1, k / 2);
int p2 = k - p1;
if(nums1[base1 + p1 - 1] < nums2[base2 + p2 - 1])
{
return findKthSortedArrays(nums1, base1 + p1, len1 - p1, nums2, base2, len2, k - p1);
}
if(nums1[base1 + p1 - 1] > nums2[base2 + p2 - 1])
{
return findKthSortedArrays(nums1, base1, len1, nums2, base2 + p2, len2 - p2, k - p2);
}
//if(nums1[base1 + p1 - 1] == nums2[base2 + p2 - 1])
return nums1[base1 + p1 - 1];
}
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int totalLen = nums1.size() + nums2.size();
//判断totalLen是奇数还是偶数
if(totalLen & 0x01)
{
return findKthSortedArrays(nums1, 0, nums1.size(), nums2, 0, nums2.size(), totalLen / 2 + 1);
}
else
{
return (findKthSortedArrays(nums1, 0, nums1.size(), nums2, 0, nums2.size(), totalLen / 2) + findKthSortedArrays(nums1, 0, nums1.size(), nums2, 0, nums2.size(), totalLen / 2 + 1)) / 2;
}
}
};