Home » leet code » leet code median of two sorted array Java ,C++ ,C, JS solution

leet code median of two sorted array Java ,C++ ,C, JS solution

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Solution:

CPP

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        
        vector<int>v3;
        v3=nums1;
        v3.insert(v3.end(), nums2.begin(), nums2.end());
           double res;
        sort(v3.begin(),v3.end());
        int n=v3.size();
        if(n%2==0){
            int x=n/2;
            double a=v3[x-1];
            double b=v3[x];
            res=(a+b)/2;
             return res;
        }
        
        else{
           return res=v3[n/2];
        }
    }
};

Java Solution :

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums2.length < nums1.length)
            return findMedianSortedArrays(nums2, nums1);
        return helper(nums1, 0, nums1.length, nums2);
    }
    private double helper(int[] nums1, int l, int h, int[] nums2){
        while(l <= h){
            int m1 = l+(h-l)/2;                                                     //# of elements on left in nums1
            int m2 = (nums2.length+nums1.length+1)/2-m1;                            //# of elements on left in nums2
            if(m1 > 0 && m2 < nums2.length && nums1[m1-1] > nums2[m2])              //m1 needs to reduced
                h = m1-1;
            else if(m2 > 0 && m1 < nums1.length && nums2[m2-1] > nums1[m1])
                l = m1+1;
            else{
                int total = nums1.length+nums2.length;
                int maxLeft = -Integer.MAX_VALUE;
                if(m1 > 0)
                    maxLeft = Math.max(maxLeft, nums1[m1-1]);
                if(m2 > 0)
                    maxLeft = Math.max(maxLeft, nums2[m2-1]);
                if(total % 2 != 0)
                    return maxLeft;
                int minRight = Integer.MAX_VALUE;
                if(m1 < nums1.length)
                    minRight = Math.min(minRight, nums1[m1]);
                if(m2 < nums2.length)
                    minRight = Math.min(minRight, nums2[m2]);
                return (maxLeft+minRight)/2.0;
            }
        }
        return 0;
    }

java script Solution :

const findMedianSortedArrays = (nums1, nums2) => {
    // 1. Find the shorter array of the two lists and make it nums1
    // 2. Find a pivot point in nums1 (using binary search)
    // 3. pX + pY = (x + y + 1)/2, where x = len(nums1) and y = len(nums2)
    if(nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }
    let [x, y] = [nums1.length, nums2.length];
    let [low, high] = [0, x];

    while (low <= high) {
        let pX = Math.floor((low + high)/2);
        let pY = Math.floor((x + y + 1)/2) - pX;

        let maxLeftX = (pX === 0)? -Infinity: nums1[pX - 1];
        let minRightX = (pX === x)? Infinity: nums1[pX];
        let maxLeftY = (pY === 0)? -Infinity: nums2[pY - 1];
        let minRightY = (pY === y)? Infinity: nums2[pY];
        // Found the required condition
        if(maxLeftX <= minRightY && maxLeftY <= minRightX ) {
            let maxLeft = Math.max(maxLeftX, maxLeftY);
            let minRight = Math.min(minRightX, minRightY);
           // for even length
            if((x + y) % 2 === 0) {
                return (maxLeft + minRight)/2.0;
            }
           // for odd length
            else {
                return maxLeft;
            }
        }
        else if(maxLeftX > minRightY) {
            high = pX - 1;
        }
        else {
            low = pX + 1
        }
    }
}

Leave a Comment

Your email address will not be published. Required fields are marked *