4.寻找两个有序数组的中位数

一、思路：

要求时间复杂度为O(M+N)，采用双指针法，将两个有序数组归并到另一个数组里，返回新数组的中位数。

二、代码（C++）：

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
	vector<int> merge;    //新数组
	int i = 0, j = 0;    //双指针
	double res=0.0;
	while (i != nums1.size() && j != nums2.size())    //归并过程
	{
		if (nums1[i] <= nums2[j])
			merge.push_back(nums1[i++]);
		else
			merge.push_back(nums2[j++]);
	}
	while (i != nums1.size())
		merge.push_back(nums1[i++]);
	while (j != nums2.size())
		merge.push_back(nums2[j++]);
	if (merge.size() % 2 == 1)
		return merge[merge.size() / 2];
	res = merge[merge.size() / 2] + merge[merge.size() / 2 - 1];
	return res/2;
}