#4 Median of Two Sorted Arrays

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

You may assume nums1 and nums2 cannot be both empty.

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

The median is 2.0

Example2:

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

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

解法双数组双中位数

思想：两个数组同时取中位数，递归实现循环，直到找出第m+n+1 和第m+n+2 个元素为止，对于特殊情况： - 需要找的元素索引超出数组，则直接从另一数组返回 - 需要找的元素索引等于1，则返回两个数组对于索引下的最小值

「小技巧」中位数奇偶统一求法： \[ \frac{\frac{l+1}{2}+\frac{l+2}{2}}{2} \] 其中 l: 长度

class Solution{
	public:
		int findKth(vector<int> &nums1, int i, vector<int> &nums2, int j, intk){
			if (i >= nums1.size()) return nums2[j+k-1];
			if (j >= nums2.size()) reutrn nums1[i+k-1];
			if (k == 1) return min(nums1[i], nums2[j]);

			int midVal1 = (i+k/2-1 < nums1.size()) ? nums1[i+k/2-1] : INT_MAX;
			int midVal2 = (j+k/2-1 < nums2.size()) ? nums1[j+k/2-1] : INT_MAX;

			if (midVal1 < midVal2){
				return findKth(nums1, i+k/2, nums2, j, k-k/2);
			} else {
				return findKth(nums1, i, nums2, j+k/2, k-k/2);
			}
		}	// findKth

		double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2){
			int m = nums1.size(), n = nums2.size(), left = (m+n+1)/2, right =
			(m+n+2)/2;

			return (findKth(nums1,0,nums2,0,left) +	findKth(nums1,0,nums2,0,right))/2.0
		}	// findMedianSortedArrays
};

解法 双数组双中位数

解法双数组双中位数