Share my O(log(m+n)) solution.Easy to understand


  • 0
    T

    So, the solution is very simple.We create a new array that consists of merged nums1 and nums2 by the simple rule, we add the least element of each, iterating both of them is ascending order.(using the fact that they are sorted, the result array would be sorted too), and afterwards, we simply use the created method to find median of the sorted array.

    public class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int n=nums1.length;
            int m=nums2.length;
            double median;
    
            if(nums1.length == 0 && nums2.length ==0){
                return -1;
            }
            if(nums1.length == 0){
                return findMedian(nums2);
            }
            if(nums2.length == 0){
                return findMedian(nums1);
            }
            int[] list =new int[n+m];
            int i1=0,i2=0;
            for(int i= 0;i<n+m;++i){
                
                if(nums1[i1]<nums2[i2]){
                    list[i]=nums1[i1];
    
                    ++i1;
                }
                else{
                    list[i]=nums2[i2];
     
                    ++i2;
                }
                if(i1 == nums1.length){
                    --i1;
                    nums1[i1] = Integer.MAX_VALUE;
                }
                if(i2 == nums2.length){
                    --i2;
                    nums2[i2] = Integer.MAX_VALUE;
                }
            }
            return findMedian(list);
            
        }
        public double findMedian(int[] arr){
            int n = arr.length;
            if(n%2==0){
                return (double)((double)arr[n/2]+(double)arr[n/2-1])/2;
            }
            return arr[n/2];
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.