Header Ad

Leetcode Median of two sorted arrays problem solution

In this Leetcode Median of two sorted arrays problem solution we have 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)).

Leetcode Median of two sorted arrays problem solution


Problem solution in Python.

class Solution:
    # @return a float
    def findMedianSortedArrays(self, A, B):
        med1 = med2 = i = j = 0
        n = len(A) + len(B)
        
        while (i + j) <= n / 2:
            if i < len(A) and j < len(B):
                med2 = med1
                if A[i] < B[j]:
                    med1 = A[i]
                    i += 1
                else:
                    med1 = B[j]
                    j += 1
            elif i < len(A):
                med2 = med1
                med1 = A[i]
                i += 1
            elif j < len(B):
                med2 = med1
                med1 = B[j]
                j += 1

        if n % 2 == 0:
            return (med1 + med2) / 2.0
        else:
            return med1



Problem solution in Java.

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
       ArrayList<Integer> list = new ArrayList<Integer>();
        for(int i=0;i<nums1.length;i++)
        {
            list.add(nums1[i]);
        }
        for(int i=0;i<nums2.length;i++)
        {
            list.add(nums2[i]);
        }
        Collections.sort(list);
        int size=list.size();

        if (size % 2 == 1)   return (double) list.get(size/2);
        
          return (double) (list.get((size/2)-1) + list.get(size/2) )/2;
        
    }
}


Problem solution in C++.

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        nums1.insert(nums1.begin(), nums2.begin(), nums2.end());
        sort(nums1.begin(), nums1.end());
        
        int median = nums1.size()/2;
        if(nums1.size()%2 == 1) 
        {
            return nums1[median];
        }
        else
        {
            return (double)(nums1[median]+nums1[median-1])/2;
        }
    }


Problem solution in C.

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int len = nums1Size + nums2Size;
    int merged[len];
    int i = 0, j = 0, idx = 0;
    while (i < nums1Size || j < nums2Size) {
        if (i < nums1Size && j < nums2Size) {
            if (nums1[i] < nums2[j]) {
                merged[idx++] = nums1[i++];
            } else {
                merged[idx++] = nums2[j++];
            }
        } else if (i < nums1Size) {
            merged[idx++] = nums1[i++];
        } else {
            merged[idx++] = nums2[j++];
        }
    }
    
    if (len % 2 == 0) {
        return ((merged[len/2 - 1] + merged[len/2]) / 2.0);
    } else {
        return merged[len/2];
    }
}


Post a Comment

0 Comments