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

难易度：Hard

---

思路

这道题是要求出两个有序数组的中位数，最简单的想法应该就是合并两个数组并排序，然后最中间的数就是中位数，但是这样的算法复杂度有O(m+n)，不能达到题目要求的O(log(m+n))。

另一种方法是类似于求第k小的数。比较两个数组第k/2个数的大小： 如果相等，那么这就是第k小的数； 如果a[k/2-1]大于b[k/2-1]，可以想象的到第k小的数不会落在b[0]到b[k/2]这个区间，那么这个区间就可以删去，然后在剩下的三个部分中求； 类似的，如果a[k/2-1]小于b[k/2-1]，则删去a[k/2]前面的数。 这样就可以求出第k小的数。

如果两个数组元素数是奇数，就求第k+1个数； 如果是偶数，就求k和k+1的平均值。 这里的一个问题是，求第一个k时，vector已经删去了一部分的数，不能再用来求k+1，我的解决方法是再复制一个新的，也可以将vector的地址写在函数的参数中，调用的时候直接写从哪个位置的元素开始和结束。

需要处理的特殊值有： 1. 其中一个数组为空时，直接返回另一个数组的第k个值 2. k=1的时候，返回两个数组第一个元素的最小值 3. 测试用例中可能存在其中一个数组元素数远远小于另一个数组，这时就需要用m和k/2中较小的那个作为分界，直接用k/2在上述情况会出错。（始终将较小的数组放在第一个数组处理）。

---

代码

class Solution { public: double findKth(vector<int>& a,int m, vector<int>& b,int n,int k) { if(m == 0) return b[k-1]; if(n == 0) return a[k-1]; if(m > n) return findKth(b,n,a,m,k); if(k == 1) return min(a[0],b[0]); int sa = min(m,k/2); int sb = k-sa; if(a[sa-1] == b[sb-1]) return a[sa-1]; else if(a[sa-1] < b[sb-1]) { a.erase(a.begin(),a.begin()+sa); return findKth(a,m-sa,b,n,k-sa); } else { b.erase(b.begin(),b.begin()+sb); return findKth(a,m,b,n-sb,k-sb); } } double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int m = nums1.size(); int n = nums2.size(); vector<int> n1 = nums1; vector<int> n2 = nums2; int k = (m+n)/2; if((m+n)%2) return findKth(nums1,m,nums2,n,k+1); else return (findKth(nums1,m,nums2,n,k)+findKth(n1,m,n2,n,k+1))/2; } };