leetcode 4. Median of Two Sorted Arrays

Seawolf

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

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if(m > n){
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
            int temp1 = m;
            m = n;
            n = temp1;
        }
        
        if(m == 0){
            if(n % 2 ==0) return (nums2[n/2 - 1] + nums2[n/2])/2.0;
            else return nums2[n/2]/1.0;
        }
        
        int start = 0;
        int end = m;
        int maxleft = 0;
        int minright = 0;
        int half = (m+n+1)/2;
        
        while (start <= end){
            int i = (start + end)/2;
            int j = half - i;
            if(i > 0 && nums1[i-1] > nums2[j]){
                end = i - 1;
            }
            else if (i < m && nums1[i] < nums2[j-1]){
                start = i + 1;
            }
            else{
                if(i == 0) maxleft = nums2[j-1];
                else if (j == 0) maxleft = nums1[i-1];
                else maxleft = Math.max(nums2[j-1], nums1[i-1]);
                
                if(i == m) minright = nums2[j];
                else if (j == n) minright = nums1[i];
                else minright = Math.min(nums2[j], nums1[i]);
                
                if((m+n) % 2 == 0) return (minright + maxleft)/2.0;
                else return maxleft/1.0;
            }
        }
        
        return -1.0;
    }
}

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m = len(nums1)
        n = len(nums2)
        if(m > n):
            temp = nums1
            nums1 = nums2
            nums2 = temp
            temp1 = m
            m = n
            n = temp1
        
        
        if(m == 0):
            if(n % 2 ==0):
                return (nums2[int(n/2) - 1] + nums2[int(n/2)])/2.0
            else:
                return (nums2[int(n/2)])/1.0
        
        
        start = 0
        end = m
        maxleft = 0
        minright = 0
        half = int((m+n+1)/2)
        
        while (start <= end):
            i = int((start + end)/2)
            j = half - i
            if(i > 0 and nums1[i-1] > nums2[j]):
                end = i - 1
            
            elif (i < m and nums1[i] < nums2[j-1]):
                start = i + 1
            
            else:
                if(i == 0):
                    maxleft = nums2[j-1]
                elif (j == 0):
                    maxleft = nums1[i-1]
                else:
                    maxleft = max(nums2[j-1], nums1[i-1])
                
                if(i == m):
                    minright = nums2[j]
                elif (j == n):
                    minright = nums1[i]
                else:
                    minright = min(nums2[j], nums1[i])
            
        
        
                if((m+n) % 2 == 0):
                    return (minright + maxleft)/2.0
                else:
                    return maxleft/1.0