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

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

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例 3：

输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

示例 4：

输入：nums1 = [], nums2 = [1]
输出：1.00000

示例 5：

输入：nums1 = [2], nums2 = []
输出：2.00000

解题思路

先判断极端情况,即第一个容器为空或者第二个容器为空.为空时需要判断是否只有一个数的情况.
如果时其他情况下,两容器长度相加后除以2再加1,然后设置一个新容器,容器的大小就等于该值.可以通过比较两个容器的最小值,放到新容器中;
最后判断容器长度为偶数还是奇数,如果时偶数需要新容器最后两位相加除以2,如果为奇数就为最后一位;
判断特殊情况比较冗余,看别的大佬合并两个容器运用双指针做,这样会快很多,极端情况也容易排除.做的过程没想到这个,还是缺乏算法知识;

运行结果

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KS08vVh8-1624769103377)(C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20210627124327290.png)]

代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
	double count = 0.0;

	if (nums1.size() == 0)
	{
		if (nums2.size() == 1)
		{
			count = (double)nums2[0];
		}
		else
		{
			int max = nums2.size() / 2;
			if (nums2.size() % 2 == 0)
			{
				count = (double)(nums2[max] + nums2[max - 1]) / 2;
			}
			else
			{
				count = (double)nums2[max];
			}
		}
	}
	else if(nums2.size() == 0)
	{
		if (nums1.size() == 1)
		{
			count = (double)nums1[0];
		}
		else
		{
			int max = nums1.size() / 2;
			if (nums1.size() % 2 == 0)
			{
				count = (double)(nums1[max] + nums1[max - 1]) / 2;
			}
			else
			{
				count = (double)nums1[max];
			}
		}
	}
	else
	{
		int max = (nums1.size() + nums2.size()) / 2 + 1;
		bool isDouble = true;

		if ((nums1.size() + nums2.size()) % 2 == 0)
		{
			isDouble = true;
		}
		else
		{
			isDouble = false;
		}
		vector<int>c;
		int indexa = 0;
		int indexb = 0;
		bool a = false;
		bool b = false;
		for (int i = 0; i < max; i++)
		{
			if (nums1[indexa] <= nums2[indexb])
			{
				c.push_back(nums1[indexa]);
				indexa += 1;
				if (indexa == nums1.size())
				{
					a = true;
					break;
				}
			}
			else
			{
				c.push_back(nums2[indexb]);
				indexb += 1;
				if (indexb == nums2.size())
				{
					b = true;
					break;
				}
			}
		}

		if (a)
		{
			int y = max - c.size();
			for (int i = 0; i < y; i++)
			{
				c.push_back(nums2[indexb]);
				indexb++;
			}
		}
		else if (b)
		{
			int y = max - c.size();
			for (int i = 0; i < y; i++)
			{
				c.push_back(nums1[indexa]);
				indexa++;
			}
		}


		if (isDouble)
		{
			count = (double)(c[max - 1] + c[max - 2]) / 2;
		}
		else
		{
			count = (double)c[max - 1];
		}
	}
	return count;
    }
};