Easy accepted JAVA solution for: Median of Two Sorted Arrays:run time :640 ms


  • 0
    X

    public class Solution {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

         int[] total = new int[nums1.length+nums2.length];
         int i1 = 0;  
         int i2 = 0;
         double median = 0;
      for (int i = 0; i < nums1.length+nums2.length; i++) {
       if (nums1.length==0){
    	   total[i]=nums2[i2];
           i2++;
           }
       else if (nums2.length==0){
    	   total[i]=nums1[i1];
           i1++;
           }
       else {
           if (i1>=nums1.length && i2<nums2.length) {
        	   total[i]=nums2[i2];
               i2++;
               } 
           else if (i2>=nums2.length && i1<nums1.length) {   
        	   total[i]=nums1[i1];
               i1++;
               }
           else {
                if(nums1[i1]<=nums2[i2]){   
                	total[i]=nums1[i1];
        	        i1++;
        	        }
        		
        	    else  if (nums1[i1]>nums2[i2]){
        	    	total[i]=nums2[i2];
                    i2++;
                    }
                }
           } 
       }
      if(total.length==0)
    	  median=0;
      else if(total.length==1)
    	  median=total[0];
      else if(total.length==2)
    	  median=(double)(total[0]+total[1])/2;
      else {
    	  if (total.length%2==1)
    		  
    		  median= (double)total[total.length/2];
    	  if (total.length%2==0)
    		  median = (double)(total[total.length/2]+total[total.length/2-1])/2;
    	  }    	 
      return median;
         
        }
    

    }


  • 0
    K

    i dont think this solution's run time complexity could be O(log (m+n)).


  • 2
    H

    it can be optimized without total

    public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int nums1Size=nums1.length;
    	int nums2Size=nums2.length;
    	int mid = (nums1Size+nums2Size)/2;
    	if(mid==0){
    		if(nums1Size==0 && nums2Size>0)
    			return nums2[0];
    		if(nums2Size==0 && nums1Size>0)
    			return nums1[0];
    		return 0;
    	}
    	int i=0,j=0,l=0,l1=0,l2=0,odd=0,cur=0;
    	if((nums1Size+nums2Size)%2==0) odd=1;
    	else mid++;
    	while(l<=mid){
    		if(i>=nums1Size && j<nums2Size){
    			cur=nums2[j];
    			j++;
    		}else if(j>=nums2Size && i<nums1Size){
    			cur=nums1[i];
    			i++;
    		}else{
    			if(nums1[i]<nums2[j]){
    				cur=nums1[i];
    				i++;
    			}else{
    				cur=nums2[j];
    				j++;
    			}
    		}
    
    		if(l==mid-1){
    			if(odd==1){
    				l1=cur;
    			}else{
    				return cur;
    			}
    		}
    		if(l==mid){
    			l2=cur;
    		}
    		l++;
    	}
    	return (l1+l2)/2.0;
       }
    }

Log in to reply
 

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