Easy Java Code : O(1) space complexity and O(n) time complexity


  • 0
    B

    public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    /*
    * Suppose the total number of elements are odd,
    * so we have to return the middle element,
    * else we have to return average of middle
    * element and one before that.
    *
    * Part 1 of the code helps to reach that element
    * which is just before the median.
    * Since the total number of elements can be even
    * we may need the element before median.
    * So we will keep a copy of the last element in
    * 'last' variable.
    *
    * Part 2 will check if the total input elements
    * are even or odd. It will also check
    * if any of the input arrays have got exhausted
    * or not. If one of them has got
    * exhausted then middle element will be in the other array
    *
    *
    */

        int last=0, totalLength = nums1.length+nums2.length, j=0, index1=0, index2=0;
    
        if(nums1.length==0 && nums2.length==0 ) return 0; 
    
        while(j<totalLength/2 && index1<nums1.length && index2<nums2.length){
    	if(nums1[index1] > nums2[index2])  last=nums2[index2++];
    	else last=nums1[index1++];
    	j++;
    }
    	 
    while(j<totalLength/2 && index1<nums1.length){
    	last=nums1[index1++]; 
    	j++;
    }
    	 
    while(j<totalLength/2 && index2<nums2.length){
    	last=nums2[index2++]; 
    	j++;
    }
    	 
    if(totalLength%2 != 0){
    	if(index1 == nums1.length) return (double)nums2[index2];
    	if(index2 == nums2.length) return (double)nums1[index1];
    	if(nums1[index1] > nums2[index2]) return (double)nums2[index2];
    	else	return (double)nums1[index1];
    }
    	 
    else{
    	if(index1 == nums1.length) return (double)(nums2[index2]+last)/2;
    	if(index2 == nums2.length) return (double)(nums1[index1]+last)/2;
    	if(nums1[index1] > nums2[index2]) return (double)(nums2[index2]+last)/2;
    	else	return (double)(nums1[index1]+last)/2;
    }
    

    }

    }


  • 1
    P

    Bro, you have to solve it in O(log(m+n)). What is?


Log in to reply
 

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