LeetCode刷题（C++）——Median of Two Sorted Arrays（Hard）

缺乏、安全感 2022-06-16 01:08 134阅读 0赞

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

**时间复杂度为O(nlogn)的解法**

class Solution {
    public:
    	/*时间复杂度为O(nlogn)，空间复杂度为O(n)*/
    	double findMedianSortedArrays_1(vector<int>& nums1, vector<int>& nums2) {
    		int len1 = nums1.size();
    		int len2 = nums2.size();
    		if (len1 == 0 && len2 == 0)
    			return 0;
    		if (len1 == 0 && len2 == 1)
    			return nums2[0];
    		if (len1 == 1 && len2 == 0)
    			return nums1[0];
    		vector<int> nums;
    		for (int i = 0; i < len1;i++)
    			nums.push_back(nums1[i]);
    		for (int i = 0; i < len2;i++)
    			nums.push_back(nums2[i]);
    		sort(nums.begin(), nums.end());
    		int len = nums.size();
    		if ((len & 1) == 1)
    			return nums[len / 2];
    		else
    		{
    			return (nums[len / 2 - 1] + nums[len / 2]) / 2.0;
    		}
    	}
    
    };

**时间复杂度为O(n)的解法：设置两个指针分别指向数组a和b，然后同时遍历两个数组，计数，寻找中位数**

class Solution {
    public:
    	/*时间复杂度为O(n)的解法*/
    	//设置两个指针同时遍历两个数组，计数，找到中位数
    	double findMedianSortedArrays_2(vector<int>& nums1, vector<int>& nums2) {
    		int len1 = nums1.size();
    		int len2 = nums2.size();
    		if (len1 == 0 && len2 == 0)
    			return 0;
    		int median = (len1 + len2) / 2;
    		bool flag = (len1 + len2) & 1;
    		int i = 0, j = 0;
    		while (i < len1&&j < len2)
    		{
    			if (nums1[i] < nums2[j])
    			{
    				median--;
    				if (median == 0)
    				{
    					if (flag)
    						return nums1[i];
    					else
    					{
    						if (nums1[i + 1] < nums2[j])
    							return (nums1[i] + nums1[i + 1]) / 2.0;
    						else
    							return (nums1[i] + nums2[j]) / 2.0;
    					}
    				}
    				i++;
    			}
    			else
    			{
    				median--;
    				if (median == 0)
    				{
    					if (flag)
    						return nums1[j];
    					else
    					{
    						if (nums1[j + 1] < nums2[i])
    							return (nums1[j] + nums1[j + 1]) / 2.0;
    						else
    							return (nums1[i] + nums2[j]) / 2.0;
    					}
    				}
    				j++;
    			}
    		}
    		if (i + j < median)
    		{
    			if (i == len1)
    				return nums2[median - (i + j)];
    			else
    				return nums1[median - (i + j)];
    		}
    	}
    };

**时间复杂度为O(log(m+n))的解法：**

**思路：例如数组 a=\[1,3,5,7,9\]，长度m=5， 数组起始位置下标为 l1，终止位置下标为 r1**

**数组 b=\[2,4,6,8\]， 长度n=4，**  **数组起始位置下标为 l2，终止位置下标为 r2**

**数组 c=\[1,2,3,4,5,6,7,8,9\]**

**中位数为数组c的中间位置的数，即下标为 k=（m+n-1）/2=4 的数（数组c的第五个数(k+1)）**

**（1）比较两个数组中间位置的数，a\[m1\]和b\[m2\] ,其中 m1=(l1+r1)/2，m2=(l2+r2)/2**

**A: 如果a\[m1\]>b\[m2\]，比较数组a的前半部分和数组b的前半部分组成的序列个数是否大于要查找的第K个数**

**如果大于，则说明要找的数一定不在数组a的后半部分，此时递归去数组a的前半部分和数组b组成的有序数组中查找第k+1个数，即下标为k的数**

**如果小于，则说明要找的数一定不在数组b的前半部分，此时递归去数组a和数组b的后半部分组成的有序数组中查找第（(k+1)-数组b前半部分元素个数）个数，即下标为k-(m2-l2+1)的数字**

**B: 如果a\[m1\]<b\[m2\]，比较数组a的前半部分和数组b的前半部分组成的序列个数是否大于要查找的第K个数**

**如果大于，则说明要找的数一定不在数组b的后半部分，此时递归去数组b的前半部分和数组a组成的有序数组中查找第k+1个数，即下标为k的数**

**如果小于，则说明要找的数一定不在数组a的前半部分，此时递归去数组b和数组a的后半部分组成的有序数组中查找第（(k+1)-数组a前半部分元素个数）个数，即下标为k-(m1-l1+1)的数字**

**比如上面的例子数组a和b，要查找的数字为第5个数字（k=4）**

**中间数字 a\[2\]>b\[1\]**

**a和b前半部分总个数为5，不大于要查的第5个数，那么就说明第5个数一定不在b的前半部分，去掉b的前半部分数据，递归去a和b的后半部分数据中（1,3,5,6,7,8,9）查找第5-2=3个数，下标为2的数，此时为5，就是我们要找的中位数。**

代码如下：

class Solution {
    public:
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            int m = nums1.size();
    		int n = nums2.size();
    		if (((m + n) & 1) == 1)
    			return findKth((m + n - 1) / 2, nums1, 0, m - 1, nums2, 0, n - 1);
    		else
    		{
    			int x = findKth((m + n) / 2 - 1, nums1, 0, m - 1, nums2, 0, n - 1);
    			int y = findKth((m + n) / 2, nums1, 0, m - 1, nums2, 0, n - 1);
    			return (x + y) / 2.0;
    		}
    	}
    
    	int findKth(int k, vector<int> a, int l1, int r1, vector<int> b, int l2, int r2)
    	{
    		if (l1 > r1)
    			return b[l2 + k];
    		if (l2 > r2)
    			return a[l1 + k];
    		int m1 = (l1 + r1) / 2;
    		int m2 = (l2 + r2) / 2;
    		if (a[m1] > b[m2])
    		{
    			if (k + 1 < m1 - l1 + 1 + m2 - l2 + 1)
    				return findKth(k, a, l1, m1 - 1, b, l2, r2);
    			else
    				return findKth(k-(m2-l2+1), a, l1, r1, b, m2 + 1, r2);
    		}
    		else
    		{
    			if (k + 1 < m1 - l1 + 1 + m2 - l2 + 1)
    				return findKth(k, a, l1, r1, b, l2, m2 - 1);
    			else
    				return findKth(k - (m1 - l1 + 1), a, m1 + 1, r1, b, l2, r2);
    		}
        }
    };