The solution which beats 100.00% of cpp coders.


  • -1
    B
    class Solution 
    {
    public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
    {
    	if(nums1.size()==0 && nums2.size()==0){return 0;}
    	if(nums1.size()<nums2.size()){return findMedianSortedArrays(nums2,nums1);}
    	int n=nums1.size();
    	int m=nums2.size();
    	int formerHalfLength=(m+n+1)/2;
    	int imin=formerHalfLength-m;
    	int imax=formerHalfLength;
    	int i;
    	int j;
    	for(i=imin;i<=imax;i+=imax-imin)
    	{
    		j=formerHalfLength-i;
    		if(i<n && j>=1 && nums1[i]<nums2[j-1])
    		{
    			continue;
    		}
    		else if(j<m && i>=1 && nums2[j]<nums1[i-1])
    		{
    			continue;
    		}
    		else
    		{
    			double left;
    			if(i>=1 && j>=1)
    			{
    				left=max(nums1[i-1],nums2[j-1]);
    			}
    			else if(i<1)
    			{
    				left=nums2[j-1];
    			}
    			else {left=nums1[i-1];}
    			if((m+n)%2==0)
    			{
    				double right;
    				if(i<n && j<m)
    				{
    					right=min(nums1[i],nums2[j]);
    				}
    				else if(i==n)
    				{
    					right=nums2[j];
    				}
    				else {right=nums1[i];}
    				return (left+right)/2;
    			}
    			else
    			{
    				return left;
    			}
    		}
    	}
    
    	imin++;
    	imax--;
    	while(true)
    	{
    		i=(imin+imax)/2;
    		j=formerHalfLength-i;
    		if(nums1[i]<nums2[j-1])
    		{
    			imin=i+1;
    		}
    		else if(nums2[j]<nums1[i-1])
    		{
    			imax=i-1;
    		}
    		else
    		{
    			double left=max(nums1[i-1],nums2[j-1]);
    			
    			if((m+n)%2==0)
    			{
    				double right=min(nums1[i],nums2[j]);
    				return (left+right)/2;
    			}
    			else
    			{
    				return left;
    			}
    		}
    	}
    }
    };

Log in to reply
 

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