Leetcode: Median of Two Sorted Arrays

Difficulty: Hard

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)).

Subscribe to see which companies asked this question

Hide Tags

 Divide and Conquer Array Binary Search

--------------------------------------------------

//Binary search with two arrays
// l1, m1, r1;
// l2, m2, r2;
// try to find the Kth elements using binary search: keep the most left part while discard the most right part (there are total 4 parts in each round)


class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int size1=nums1.size(), size2=nums2.size(), size=size1+size2, k=size/2;
        int l1=0, l2=0, r1=nums1.size()-1, r2=nums2.size()-1, m1=(l1+r1)/2, m2=(l2+r2)/2;
        int even=size%2, cnt=0;//even==0 is even
        //corner case
        //if(size1==0)....
        //if(size2==0)....
        int max=nums1[0]>nums2[0]?nums2[0]:nums1[0], max_pre=max;
        //normal cases    
        while(true){
            if(nums1[m1]>nums2[m2]){
                cnt+=m2-l2+1;
                l2=m2+1;
                m2=(l2+r2)/2;
                //
                r1=m1; 
                m1=(l1+r1)/2;
                max_pre=max;
                max=max>nums2[m2]?max:nums2[m2];
            }
            else{
                cnt+=m1-l1+1;
                l1=m1+1;
                m1=(l1+r1)/2;
                //
                r2=m2;
                m2=(r2+l2)/2;
                max_pre=max;
                max=max>nums1[m1]?max:nums1[m1];
            }
            //
            if(cnt==k && even ==0 ) return (max+max_pre)/2;
            if(cnt==k && even ==1 )return max;      
        }
    }

};














Merge the two and find the Kth element. 

Don't need to merge all, only need to merge the first Kth element. 

//////////////////////////////////////////////////////

//codes:

class Solution {

 public:

        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

               int len1 = nums1.size(), len2 = nums2.size(), i = 0, j = 0, mid1 = 0, mid2 = 0, count = 0;

               //check input

               if (len1 + len2 == 0)return NULL;

               while (1){

                      count++;

                      if (count == (len1 + len2) / 2){

                            if (i == len1) { mid1 = nums2[j]; j++; }

                            else if (j == len2) { mid1 = nums1[i]; i++; }

                            else if (nums1[i]<nums2[j]) { mid1 = nums1[i]; i++; }

                            else { mid1 = nums2[j]; j++; }

                            continue;

                      }

                      else if (count == (len1 + len2) / 2 + 1){

                            if (i == len1) { mid2 = nums2[j]; j++; }

                            else if (j == len2) { mid2 = nums1[i]; i++; }

                            else if (nums1[i]<nums2[j]) { mid2 = nums1[i]; i++; }

                            else { mid2 = nums2[j]; j++; }

                            break;

                      }

                      //updtate the index

                      if (i == len1) { j++; }

                      else if (j == len2) { i++; }

                      else if (nums1[i]<nums2[j]) { i++; }

                      else { j++; }

               }

               //calculate median

               double fn = (len1 + len2) % 2 == 0 ? double(mid1 + mid2) / 2 : mid2;

               return fn;

        }

 };