My 20ms solution in C


  • 0
    S
    double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) 
    {
        double rtVal;
    	int i1, i2, csum, sum;
    	int targetL=0, targetR=0;
    	
    	sum=nums1Size+nums2Size;
    	if(1 == (sum & 1))
    	{
    		if(1 != sum)
    		{
    			targetL = (sum - 1)/2;
    			targetR = targetL;
    		}
    		else
    		{
    			if(1==nums1Size)
    				return nums1[0];
    			else
    				return nums2[0];
    		}
    	}
    	else
    	{
    		targetL = (sum - 1)>>1;
    		targetR = targetL+1;
    	}
    	i1=0;i2=0;csum=0;
    	
    	while(csum<sum)
    	{
    		int addVal=0;
    		if(i1>=nums1Size)
    		{
    			addVal = nums2[i2];
    			i2++;
    		}
    		else if(i2>=nums2Size)
    		{
    			addVal = nums1[i1];
    			i1++;
    		}
    		else
    		{
    			if(nums1[i1]<=nums2[i2])
    			{
    				addVal = nums1[i1];
    				i1++;
    			}
    			else
    			{
    				addVal = nums2[i2];
    				i2++;
    			}
    		}
    		csum++;
    		if(targetL==(csum-1))
    			rtVal = addVal;
    		if(targetR==(csum-1))
    		{
    			rtVal += addVal;
    			break;
    		}
    	}
    	rtVal /= 2;
    	return rtVal;
    }

  • -1
    S
    Your Solution is good but 20 ms is high of C. Here is 14 ms Java Solution. Try implementing in C might reduce the execution time even further.
    
    
    
    
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
                if( nums1.length == 0 && nums2.length == 0){
                    return -1;
                }
                if( nums1.length == 0){
                    if( nums2.length % 2 == 0){
                        return ((double)nums2[ (nums2.length-1) / 2] + (double)nums2[ (nums2.length-1) / 2 + 1])/2.0;
                    }
                    else{
                        return (double)nums2[ (nums2.length-1) / 2];
                    }
                }
                if( nums2.length == 0){
                    if( nums1.length % 2 == 0){
                        return ((double)nums1[ (nums1.length-1) / 2] + (double)nums1[ (nums1.length-1) / 2 + 1])/2.0;
                        
                    }
                    else{
                        return (double)nums1[ (nums1.length-1) / 2];
                    }
                }
                if(nums1.length<=nums2.length)
                    return findMedianTwoArray( nums1, nums2, 0, nums1.length-1, 0, nums2.length-1);
                else
                    return findMedianTwoArray( nums2, nums1, 0, nums2.length-1, 0, nums1.length-1);
            }
            
            public double findMedianTwoArray( int[] nums1, int[] nums2, int start1, int end1, int start2, int end2){
                int len1 = (end1-start1)+1;
                int len2 = (end2-start2)+1;
                if(len1 == 1 || len2 == 1){
                    if(len1==len2){
                        return ((double)(nums1[start1]+nums2[start2])/2.0);
                    }
                    else{
                        if(len2%2==0){
                            if(nums1[start1] < nums2[start2+(end2-start2)/2]){
                                return (double)nums2[start2+(end2-start2)/2];
                            }
                            else if(nums1[start1] > nums2[start2+(end2-start2)/2+1]){
                                return (double)nums2[start2+(end2-start2)/2+1];
                            }
                            else
                                return (double)nums1[start1];
                        }
                        else{
                            if(nums1[start1] < nums2[start2 + (end2-start2)/2-1]){
                                return (double)(nums2[start2 + (end2-start2)/2-1] + nums2[start2 + (end2-start2)/2])/2.0;
                            }
                            else if(nums1[start1] < nums2[start2 + (end2-start2)/2] || nums1[start1] < nums2[start2 + (end2-start2)/2+1]){
                                return (double)(nums1[start1]+nums2[start2 + (end2-start2)/2])/2.0;
                            }
                            else
                                return (double)(nums2[start2 + (end2-start2)/2+1] + nums2[start2 + (end2-start2)/2])/2.0;
                        }
                    }
                }
                else if(len1==2 || len2 == 2){
                    if(len1==len2){
                        return findMedian4ele(nums1[start1],nums1[end1],nums2[start2],nums2[end2]);
                    }
                    else{
                        if(len2%2==0){
                            int num3 = (nums2[start2 + (end2-start2)/2-1]>nums1[start1]?nums2[start2 + (end2-start2)/2-1]:nums1[start1]);
                            int num4 = (nums2[start2 + (end2-start2)/2+2]<nums1[end1]?nums2[start2 + (end2-start2)/2+2]:nums1[end1]);
                            return findMedian4ele(nums2[start2 + (end2-start2)/2],nums2[start2 + (end2-start2)/2+1], num3, num4);
                        }
                        else{
                            return findMedian5ele( nums1[start1],nums1[end1],nums2[start2+(end2-start2)/2],nums2[start2+(end2-start2)/2-1],nums2[start2+(end2-start2)/2+1]);
                        }
                    }
                }
                else{
                    double mid1 = computeMedian( nums1, start1, end1);
                    double mid2 = computeMedian( nums2, start2, end2);
                    if( mid1==mid2)
                        return mid1;
                    else if( mid1<mid2){
                        return findMedianTwoArray(nums1, nums2, start1 + (end1-start1)/2, end1, start2, end2 - (end1-start1)/2);
                }
                    else
                        return findMedianTwoArray(nums1, nums2, start1, start1 + ((end1-start1)%2==0?(end1-start1)/2:(end1-start1)/2+1) , start2 + (end1-(((end1-start1)%2==0?(end1-start1)/2:(end1-start1)/2+1)+start1)), end2);
                }
            }
            
            public double findMedian4ele(int a1, int a2, int a3, int a4 ){
                ArrayList<Integer> li = new ArrayList<Integer>();
                li.add(a1);
                li.add(a2);
                li.add(a3);
                li.add(a4);
                Collections.sort(li);
                return (double)(li.get(1)+li.get(2))/2.0;
                }
            
            public double findMedian5ele(int a1, int a2, int a3, int a4, int a5 ){
                ArrayList<Integer> li = new ArrayList<Integer>();
                li.add(a1);
                li.add(a2);
                li.add(a3);
                li.add(a4);
                li.add(a5);
                Collections.sort(li);
                return (double)(li.get(2));
                }
            public double computeMedian(int[] nums, int start, int end){
                double mid = 0;
                if( (end-start)% 2==0)
                    mid = (double)nums[start+(end-start)/2];
                else
                    mid = ((double)nums[start+ (end-start)/2] + (double)nums[start+(end-start)/2 + 1])/2.0;
            
                return mid;
            }

  • 0
    T

    Good. But you algorithm is O(m + n)...


Log in to reply
 

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