【算法题】两个排序数组的中位数

喜欢ヅ旅行 2022-05-25 07:58 177阅读 0赞

**问题：**

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。

请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。

示例 1:

nums1 = [1, 3]
    nums2 = [2]
    
    中位数是 2.0

示例 2:

nums1 = [1, 2]
    nums2 = [3, 4]
    
    中位数是 (2 + 3)/2 = 2.5

**思路：**

当看到题目中给了有序的数组，那说明这种题目通过一个循环就可以搞定排序了。下面说说思路，每次循环都选取一个较小的数放在专门的数组（就是另外自己定义的数组）中，简而言之就是你小你先进去，我大了点等下一次机会，下一次如果还没有轮到我，我就一直等下去，千万不要交叉进入。

**代码：**

#include <iostream>
    #include <vector>
    using namespace std;
    
    
    
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            int len1 = nums1.size(),len2 = nums2.size();
    		int n_iter1=0,n_iter2 =0;
    		vector<int> all_num;
    		while(n_iter1 < len1 || n_iter2 < len2)//当两个容器都遍历到了末尾
    		{
    			if(n_iter1 >= len1)//首先要判断vector是否被遍历完成，免得越界
    			{
    				all_num.push_back(nums2[n_iter2]);
    				n_iter2++;
    			}
    			else if(n_iter2 >= len2)
    			{
    				all_num.push_back(nums1[n_iter1]);
    				n_iter1++;
    			}
    			else if(nums1[n_iter1] < nums2[n_iter2])//比较大小，小的先进
    			{
    				all_num.push_back(nums1[n_iter1]);
    				n_iter1++;
    			}
    			else
    			{
    				all_num.push_back(nums2[n_iter2]);
    				n_iter2++;
    			}
    		}
    		/*for(int i =0 ;i<all_num.size();i++)
    		{
    			printf("%d ",all_num[i]);
    		}
    		printf("\n");*/
    		if(all_num.size()%2 == 0)//如果容器大小是偶数
    		{
    			return float(all_num[all_num.size()/2]+all_num[all_num.size()/2-1])/2;
    		}
    		else
    		{
    			
    			return all_num[all_num.size()/2];
    		}
    
    }
    
    
    int main()
    {
    	int a[5] = {1,2};
    	int b[5] = {3,4};
    	vector<int> nums1(a,a+2);
    	vector<int> nums2(b,b+2);
    	printf("%f\n",findMedianSortedArrays(nums1,nums2));
    	return 0;
    }