My horrible C++ code using 55ms, ugly enough...though it's an O(m+n)/2 solution


  • 0
    B
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int len1 = nums1.size();
    int len2 = nums2.size();
    if (len1==0 &&len2==0)
    {return 0;}
    else if (len1==1 && len2==1)
    {return ((double)nums1[0] + (double)nums2[0]) / 2;}
    else if (len2==0)
    {
    	return (len1 % 2 == 0) ? (((double)nums1[len1 / 2] + (double)nums1[len1 / 2 - 1]) / 2) : nums1[len1 / 2 ];
    }
    else if (len1 == 0 )
    {
    	return (len2 % 2 == 0) ? (((double)nums2[len2 / 2] + (double)nums2[len2 / 2 - 1]) / 2) : nums2[len2 / 2 ];
    }
    int len = len1 + len2;
    bool even = (len % 2 == 0) ? true : false;
    int i=0, j=0;
    int median = even?(len/2):(len/2+1);
    bool throw1 = false;
    bool throw2 = false;
    for (int counter = 0; counter < len;counter++)
    {
    	if (median==(i+j+1))
    	{
    		break;
    	}
    	if (i>=(len1-1) && j<(len2-1))
    	{
    		if (nums1[i]<=nums2[j])
    		{
    			throw1 = true;
    		}
    		j++;
    	}
    	else if (j>=(len2-1) && i<(len1-1))
    	{
    		if (nums1[i] >= nums2[j])
    		{
    			throw2 = true;
    		}
    		i++;
    	}
    	else if (nums1[i]<=nums2[j])
    	{
    		i++;
    	}
    	else
    	{
    		j++;
    	}
    }
    if (!even)
    {
    	if (throw1)
    	{
    		return nums2[j-1];
    	}
    	else if ( throw2)
    	{
    		return nums1[i-1];
    	}
    	else /*if (i < (len1 - 1) && j < (len2 - 1))*/
    	{
    		return (nums1[i] < nums2[j] ? nums1[i] : nums2[j]);
    	}
    }
    else
    {
    	if (throw1)
    	{
    		return	(((double)nums2[j]+(double)nums2[j-1])/2);
    	}
    	else if (throw2)
    	{
    		return	(((double)nums1[i] + (double)nums1[i - 1]) / 2);
    	}
    	else
    	{
    		if (i==(len1-1))
    		{
    			if (nums1[i]<nums2[j+1])
    			{
    				return (((double)nums1[i] + (double)nums2[j]) / 2);
    			} 
    			else
    			{
    				return (((double)nums2[j+1] + (double)nums2[j]) / 2);
    			}
    		} 
    		else if (j==(len2-1))
    		{
    			if (nums2[j] < nums1[i + 1])
    			{
    				return (((double)nums1[i] + (double)nums2[j]) / 2);
    			}
    			else
    			{
    				return (((double)nums1[i + 1] + (double)nums1[i]) / 2);
    			}
    		}
    		else
    		{
    			if ((nums1[i] <= nums2[j + 1]) && (nums1[i + 1] >= nums2[j]))
    			{
    				return((double)nums1[i] + (double)nums2[j]) / 2;
    			}
    			else if (nums2[j]>nums1[i+1])
    			{
    				return((double)nums1[i] + (double)nums1[i+1]) / 2;
    			}
    			else
    			{
    				return((double)nums2[j] + (double)nums2[j + 1]) / 2;
    			}
    		}
    	}
    }
    

    }


  • 0
    B

    It's just too complicated to understand.

    And someone gave an better solution, by using two variables to record the smallest two number in each "for" turn.

    With additonal information, you don't need to use so many "if...else..." any more.


Log in to reply
 

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