题目
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
题目分析
这是一道很经典的题目。更为通用的形式为给定两个已经排序好的数组，找到两者所有元素中第K个元素。
针对本题，找两个已知排序数组的中位数，如果两个数组长度和为len,若
- len为偶数，则寻找第len/2与len/2+1元素之和的一半
- len为奇数，则寻找第len/2+2的元素
解题方法
给出寻找第K大元素的通用解法
常规做法1
由于两个数组已经排序，直接merge两个数组，然后取出所需元素即可。
常规解法2
由于数组已排序，且只需获得第K个元素，故使用两个整数i和j分别指向数组A和B的起始位置，整数m记录当前遍历的元素个数，if(A[i]<B[j]) i++；m++,否则j++;m++;当m==k时，取出元素即为所求
类二分查找求解方法
考虑到数组有序，采用类似二分查找的方法，每次从数组中删除K/2个元素。
假设A和B的元素个数都大于k/2，则将A中第k/2个元素（即A[K/2-1])和B中第K/2个元素(即B[k/2-1])进行比较，可考虑如下三种情况（假设K为偶数)：
- A[K/2-1]<B[K/2-1] 此时A[0]至A[K/2-1]均在A U B 的K个元素范围内，故可删去
- A[K/2-1]>B[K/2-1] 此时B[0]至B[K/2-1]均在A U B 的K个元素范围内，故可删去
- A[K/2-1]>B[K/2-1] 此时找到第K个元素，直接返回A[K/2-1]
上述过程针对k为奇数和偶数均成立，可自行推导
所以如果要查找第K个元素，可以写一个递归函数，递归函数停止的条件为
- 当A或B为空时，直接返回B[K-1]或A[K-1]
- 当K==1时，返回min(A[0],B[0])
- 当A[K/2-1]>B[K/2-1]时，返回A[K/2-1]或B[k/2-1]
解题代码
class Solution {
private:
double findKelement(vector<int>& nums1, vector<int>& nums2,int i1,int i2,int j1,int j2,int k ){
if(i1>=i2) return nums2[j1+k-1]; //若此时nums1已全部删除，则直接从nums2中取出所需元素即可
else if(j1>=j2) return nums1[i1+k-1]; //若此时nums2已全部删除，则直接从nums1中取出所需元素即可
else if(k==1) return min(nums1[i1],nums2[j1]); //当k==1时，停止递归，直接取出当前最小元素即可
int m1=min(i2-1,i1+k/2-1),m2=min(j2-1,j1+k/2-1); //考虑到数组剩余元素的个数可能已不足k/2
if(nums1[m1]<nums2[m2]) return findKelement(nums1,nums2,m1+1,i2,j1,j2,k-m1+i1-1);
else return findKelement(nums1,nums2,i1,i2,m2+1,j2,k-m2+j1-1);
}
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len1=nums1.size(),len2=nums2.size();
if((len1+len2)%2==0) return (findKelement(nums1,nums2,0,len1,0,len2,(len1+len2)/2)+findKelement(nums1,nums2,0,len1,0,len2,(len1+len2)/2+1)+0.0)/2;
else return findKelement(nums1,nums2,0,len1,0,len2,(len1+len2)/2+1);
}
};
