My 24ms C solution! Perfectly O(log(m+n))


  • 0
    Q
    double 
    findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) 
    {
    	int left = (nums1Size + nums2Size + 1) / 2, right = left;
    	if((nums1Size + nums2Size) % 2 == 0)
    		right++;
    	//printf("left:%d\tright:%d\n", left, right);
    	//find the left smallest element, comparing from the start of array--O(left)
    	//BETTER: left/2, left/4, left/8...
    	int i = 0, j = 0, t = left, k = (t + 1) / 2;
    	while(k > 0)
    	{
    		if(i + k > nums1Size || j + k > nums2Size)
    			break;
    		if(nums1[i+k-1] < nums2[j+k-1])	
    			i += k;
    		else
    			j += k;
    		t -= k;
    		k = (t + 1) / 2;
    	}
    	while(t > 0 && i < nums1Size && j < nums2Size)
    	{
    		if(nums1[i] < nums2[j])
    			i++;
    		else
    			j++;
    		t--;
    	}
    	if(t > 0)
    	{
    		if(i == nums1Size)
    			j += t;
    		else if(j == nums2Size)
    			i += t;
    	}
    	int mid_left, mid_right;
    	if(i > 0 && j > 0)
    		mid_left = (nums1[i-1] < nums2[j-1])?nums2[j-1]:nums1[i-1];
    	else if(i == 0)
    		mid_left = nums2[j-1];
    	else if(j == 0)
    		mid_left = nums1[i-1];
    	if(right > left)
    	{
    		if(i < nums1Size && j < nums2Size)
    			mid_right = (nums1[i] < nums2[j])?nums1[i]:nums2[j];
    		else if(i == nums1Size)
    			mid_right = nums2[j];
    		else if(j == nums2Size)
    			mid_right = nums1[i];
    	}
    	else
    		mid_right = mid_left;
    	//printf("mid_left:%d\tmid_right:%d\n", mid_left, mid_right);
    	return (mid_left + mid_right) / 2.0;
    }

  • 1
    I

    This is not a correct solution. The second while loop can run in O(m+n) time. How? If the size of nums1 is much greater than the size of nums2, half of the median can still be much much greater than the size of nums2. The first loop will break on the first iteration. And the second loop will run through the entirety of nums1 or nums2.


Log in to reply
 

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