LeetCode4：寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

①中位数分奇数和偶数两种情况考虑

②不需要真的合并两个数组，只需要找到中位数就行

③此解法的时间复杂度应该是O(min(m,n))，应该是没达到O(log(m+n))吧，但是有几次测试又很快，不懂

class Solution {
public:
	double findMedianSortedArrays(vector& nums1, vector& nums2) {
		int left = 0, right = nums1.size() + nums2.size() - 1;
		int mid = (left + right) / 2;
		int n1 = 0, n2 = 0;
		int flag = -1;
		if (nums1.size() == 0)
		{
			if (nums2.size() % 2 == 0)
				return (double)(nums2[(nums2.size() - 1) / 2] + nums2[(nums2.size() - 1) / 2 + 1]) / 2.0;
			else
				return (double)nums2[(nums2.size() - 1) / 2];
		}
		if (nums2.size() == 0)
		{
			if (nums1.size() % 2 == 0)
				return (double)(nums1[(nums1.size() - 1) / 2] + nums1[(nums1.size() - 1) / 2 + 1]) / 2.0;
			else
				return (double)nums1[(nums1.size() - 1) / 2];
		}
		while ((n1 + n2) <= mid && n1 < nums1.size() && n2 < nums2.size())
		{
			if (nums1[n1] <= nums2[n2])
			{
				n1++;
				flag = 1;
			}
			else
			{
				n2++;
				flag = 2;
			}
		}
		while ((n1 + n2) <= mid && n1 < nums1.size())
		{
			n1++;
			flag = 1;
		}
		while ((n1 + n2) <= mid && n2 < nums2.size())
		{
			n2++;
			flag = 2;
		}
		double x = flag == 1 ? (double)nums1[n1 - 1] : (double)nums2[n2 - 1];
		if (right % 2 != 0)//偶，还要一个mid+1
		{
			double y;
			if (n1 == nums1.size())
			{
				n2++;
				flag = 2;
				y = (double)nums2[n2 - 1];
			}
			else if (n2 == nums2.size())
			{
				n1++;
				flag = 1;
				y = (double)nums1[n1 - 1];
			}
			else
			{
				if (nums1[n1] <= nums2[n2])
				{
					n1++;
					flag = 1;
				}
				else
				{
					n2++;
					flag = 2;
				}
				y = flag == 1 ? (double)nums1[n1 - 1] : (double)nums2[n2 - 1];
			}
			return (x + y) / 2.0;
		}
		else
			return x;
	}
};