Median of Two Sorted Arrays

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

You may assume nums1 and nums2 cannot be both empty.

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

You may view the full question here.

Approach: As the two input arrays are already sorted, we just need to compare the elements at the head of the array and traverse the two arrays one element at a time.

//Approach 1
//Runtime: 2ms
//Memory usage: 42.3MB
class Solution {
    public double findMedianSortedArrays(int[] nums1r, int[] nums2r) {
        int mid1 = -1;
        int mid2 = -1;
        
        int[]  nums1, nums2;
        if(nums1r.length>nums2r.length){
            nums1 = nums1r;
            nums2 = nums2r;
        } else {
            nums2 = nums1r;
            nums1 = nums2r;
        }
        
        if((nums1.length + nums2.length)%2==0){
            mid2 = (nums1.length + nums2.length)/2;
            mid1 = mid2-1;
        } else {
            mid1 = (nums1.length + nums2.length)/2;
        }
        int i = 0;
        int j = 0;
        while((i+j)<=mid1){
            if((i+j)==mid1){
                if(i<nums1.length && j<nums2.length){
                    if(nums1[i]<nums2[j]){
                        mid1 = nums1[i];
                        i++;
                    } else {
                        mid1 = nums2[j];
                        j++;
                    }
                    if(mid2==-1){
                        return mid1;
                    } else {
                        if(j<nums2.length && i<nums1.length){
                            mid2 = (Math.min(nums1[i], nums2[j]));
                        } else if(i<nums1.length){
                            mid2 = nums1[i];
                        } else {
                            mid2 = nums2[j];
                        }
                        return ((float)mid1 + mid2)/2;
                    }
                } else {
                    if(mid2==-1){
                        return nums1[i];
                    } else {
                        return ((float)nums1[i] + nums1[i+1])/2;
                    }
                }
                
                
            } else {
                if(i<nums1.length && j<nums2.length){
                    if(nums1[i]<nums2[j]){
                        i++;
                    } else {
                        j++;
                    }
                } else if(i<nums1.length){
                    i++;
                } else {
                    j++;
                }
            }
        }
        return 0;
    }
}

Find more posts here.

Cheers & Chao!