Median of two sorted arrays


  • 0
    M

    Click here to see the full article post


  • -1
    G

    2 steps process.

    1. Merge 2 arrays to frame sorted array while merging ( a step of merge sort ) - O(m+n)
    2. find median ( 0(1) )
    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        	int[] c = merge(nums1, nums2);
            print(c);
        	if (c.length % 2 == 0) {
        		System.out.println( c.length );
        		return (double) (c[ c.length/2 -1 ] + c[ (c.length / 2) ]) / 2;
        	} else {           
        		return (double) c[ c.length/2 ];
        	}
                    
        }
        
        
        
        public static int[] merge(int[] a, int[] b) {
        	int c[] = new int[a.length + b.length];
        	
        	int i = 0;
        	int j = 0;
        	int k = 0;
        	while ( i < a.length && j < b.length ) {
        		if( a[i] == b[j] ) {
        			c[k] = a[i]; k++; i++;
        			c[k] = b[j]; k++; j++;
        		}
        		else if( a[i] < b[j]) {
        			c[k] = a[i]; k++; i++;
        		}
        		else if( a[i] > b[j]) {
        			c[k] = b[j]; k++; j++;
        		}
        	}
        	
        	while(i<a.length) {
        		c[k] = a[i]; k++; i++;
        	}
        	
        	while (j<b.length) {
        		c[k] = b[j]; k++; j++;
        	}
        	    	
        	return c;
        }
    }
    

  • -1
    G

    Slower but self-explanatory:

    class Solution {
        static class DualSortedListIterator {
            int[] nums1, nums2;
            int idx1 = 0, idx2 = 0;
            
            DualSortedListIterator(int[] nums1, int[] nums2) {
                this.nums1 = nums1;
                this.nums2 = nums2;
            }
            
            int length() {
                return nums1.length + nums2.length;
            }
            
            boolean hasNext() {
                return idx1 < nums1.length || idx2 < nums2.length;    
            }
            
            Integer next() {
                Integer ans = null;
                if (hasNext()) {
                    boolean takeFromNums1 = (idx1 < nums1.length) && (idx2 >= nums2.length || nums1[idx1] <= nums2[idx2]);
                    ans = takeFromNums1 ? nums1[idx1++] : nums2[idx2++];
                }
                
                return ans;
            }
        }
        
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            DualSortedListIterator iter = new DualSortedListIterator(nums1, nums2);
            int midIdx = (iter.length() - 1)/2;
            boolean isEven = (iter.length() & 1) == 0;
            int midVal = 0;
            
            for (int i = 0; i <= midIdx; i++) {
                midVal = iter.next();
            }
            
            return isEven ? (midVal + iter.next()) / 2.0 : midVal;
        }
    }
    

  • -1
    S

    class Solution {
    public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int i = 0,j = 0,t;
    double n = (nums1.size()+nums2.size())/2.0,s=0,ss=0;
    for(int k=0;k<=floor(n);k++)
    {
    if(j == nums2.size())
    {
    t = nums1[i];
    i++;
    }
    else if(i == nums1.size()||nums1[i]>nums2[j])
    {
    t = nums2[j];
    j++;
    }
    else
    {
    t = nums1[i];
    i++;
    }
    if(k>=ceil(n-1))
    {
    s+=t;
    ss+=1.0;
    }
    }
    return s/ss;
    }
    };


  • -1
    Z

    //use merge method
    class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int num1=nums1.length;
    int num2=nums2.length;
    int index=(num1+num2)/2;
    boolean IsOdd=(num1+num2)%2==1;
    if(IsOdd)
    {
    return find(nums1,num1,nums2,num2,index);
    }
    else
    {
    return (find(nums1,num1,nums2,num2,index)+find(nums1,num1,nums2,num2,index-1))/2.0;
    }

    }
    private double find(int[] nums1,int num1,int [] nums2,int num2,int k)
    {
        int i=0;
        int j=0;
        boolean is1=false;
        boolean is2=false;
        int l=0;
        for(l=0;l<=k;l++)
        {
            if(i>=num1)
            {
                is2=true;
                j++;
            }
            else if(j>=num2)
            {
                is1=true;
                i++;
            }
            else if(nums1[i]<nums2[j])
            {
                is1=true;
                i++;
            }
            else
            {
                is2=true;
                j++;
            }
        }
        if(j-1<0)
        {
            return nums1[i-1];
        }
        if(i-1<0)
        {
            return nums2[j-1];
        }
        return Math.max(nums1[i-1],nums2[j-1]);
    }
    

    }


  • 0
    H

    from heapq import merge
    class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
    """
    :type nums1: List[int]
    nums2: List[int]
    :type nums3: List[int]
    rtype: float
    """
    num3=[]

        num3=list(merge(nums1, nums2))
        print(num3)
        if(len(num3)%2!=0):
            return num3[len(num3)/2]
        else:
            return (float)(num3[len(num3)//2]+num3[(len(num3)//2)-1])/2

  • 0
    P

    There are typos in the Java code that break the time complexity. iMax should be set to i - 1 instead of iMax - 1. Similarly, iMin should be set to i + 1 instead of iMin - 1.


  • 0
    I

    class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int len1 = nums1.length;
    int len2 = nums2.length;
    int[] nums = new int[len1 + len2];
    int n = 0;
    for(int i=0,j=0;i<len1 || j<len2;) {
    if(i>=len1){
    nums[n++] = nums2[j++];
    }else if(j>=len2) {
    nums[n++] = nums1[i++];
    }else if(nums1[i] < nums2[j]){
    nums[n++] = nums1[i++];
    } else {
    nums[n++] = nums2[j++];
    }

    	}
    	
    	int x = (len1+len2)/2;
    	return (len1+len2)%2==0?
    			 new Double(nums[x-1]+nums[x])/2
    			:new Double(nums[x]) ;
    }
    

    }


  • 0
    S

    For the java solution, will it throw an exception if both arrays are empty?


Log in to reply
 

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