请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。-白红宇

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

阅读量：3924 次

发布时间：2019-05-23

本文共 1281 字，大约阅读时间需要 4 分钟。

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

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

你可以假设 nums1 和 nums2 不会同时为空。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays

class Solution {
   public:	double findMedianSortedArrays(vector
   
    & nums1, vector
    
     & nums2) {
   		int length1 = nums1.size();		int length2 = nums2.size();		int mid1 = 0; int mid2 = 0;		vector
     
       temp1 = nums1;		vector
      
        temp2 = nums2;		vector
       
         temp3 ;		if ((length1 + length2) % 2 == 0)		{
   			mid1 = (length1 + length2)/2-1;//下标			mid2 = (length1 + length2) /2;		}		else {
   			mid1=mid2= (length1 + length2) / 2;		}//		cout << mid1 << " " << mid2 << endl;		int i = 0, j = 0; int index = 0;		while (i != length1 || j != length2) {
   //只要有一个不为空			if (index <= mid2) {
   				if (i < length1&&j < length2) {
   					if (nums1[i] <= nums2[j]) {
   						temp3.push_back(nums1[i]);						i++;					}					else {
   						temp3.push_back(nums2[j]);						j++;					}				}				else if (i>=length1&&j
        
         = length2) { temp3.push_back(nums1[i]); i++; } index++; } else { break; } }// for (int t = 0; t < temp3.size(); t++) { // cout << temp3[t] << endl;// } double res; res = (double)(temp3[mid1] + temp3[mid2]) / 2; return res; }};