4. Median of Two Sorted Arrays

Median of Two Sorted Arrays

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

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

solution

class Solution {
 public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[] nums12 = new int[len1 + len2];
        int t = 0,s = 0;
        for(int i = 0; i < nums12.length; i++){
            if (t < nums1.length || s < nums2.length){
                if(t < nums1.length && s < nums2.length){
                    if(nums1[t] <= nums2[s] ){
                        nums12[i] = nums1[t];
                        t++;
                    }else{
                        nums12[i] = nums2[s];
                        s++;
                    }
                }else if(t < nums1.length){
                    nums12[i] = nums1[t];
                    t++;
                }else if(s < nums2.length){
                    nums12[i] = nums2[s];
                    s++;
                }
            }
        }
        int len = nums12.length;
        double ret = 0.0;
        if(len % 2 == 0){
            ret = (nums12[len / 2] + nums12[len / 2 - 1]) / 2.0;
        }else{
            ret = nums12[(len - 1) / 2];
        }
        return ret;
    }
}