I run the code on my vs2010 works and get correct results, but when I submit wrongly result reported


  • 0
    Z
    double findMedianSortedArrays(int A[], int m, int B[], int n)
    
        {
        	if(m==0)
        	{
        		if(n%2==0)
        			return (double(B[n/2])+double(B[n/2-1]))/2.0;
        		else
        			return double(B[(n-1)/2]);
        	}
        	
        	if(n==0)
        	{
        		if(m%2==0)
        			return (double(A[m/2])+double(A[m/2-1]))/2.0;
        		else
        			return double(A[(m-1)/2]);
        	}
        
        		if((m+n)%2==1)
        			return findKthSortedArrays(A,m,B,n,(m+n+1)/2);
        	    else
        	    {
        	        double a=findKthSortedArrays(A,m,B,n,(m+n)/2);
        	        double b=findKthSortedArrays(A,m,B,n,(m+n)/2+1);
        	        return (a+b)/2.0;
        	    }
        
        
        }  
        
    double findKthSortedArrays(int A[], int m, int B[], int n,int k)
    
        {
        	// base case
        	// trivial m or trivial n
        	if(n==0)
        		return A[k-1];
        	if(m==0)
        		return B[k-1];
        	if(m<=3&&n<=3)
        	{
        		int i;
        		vector<int> tmp;
        		for(i=0;i<m;i++)
        			tmp.push_back(A[i]);
        		for(i=0;i<n;i++)
        			tmp.push_back(B[i]);
        		sort(tmp.begin(),tmp.end());
        		return tmp[k-1];
        	}
        
        	// trivial ordering
        	if(A[0]>B[n-1])
        	{
        		if(k<=n)
        			return B[k-1];
        		else
        			return A[k-n-1];
        	}
        	else if(B[0]>A[m-1])
        	{
        		if(k<=m)
        			return A[k-1];
        		else
        			return B[k-m-1];
        	}
        
        	//find kth smallest number after merging A and B?
        	int ak = float(m)*float(k)/float(m+n)+0.5;
        	ak = (int)ak>1? ak:1;
        	int bk = k-ak;
        
        	if(A[ak-1]==B[bk-1])
        		return A[ak-1];
        	else if(A[ak-1] > B[bk-1])
        	{
        		//find A[ak-1] in B[bk-1...n-1], return new_id,new_n for B[]
        		int st=bk,ed=n-1;
        		int curr_idB = (st+ed)/2;
        		do
        		{
        			if(B[curr_idB]==A[ak-1])
        				break;
        			else if(B[curr_idB]>A[ak-1])
        			{ed = curr_idB-1; curr_idB = (st+ed)/2;}
        			else
        			{st = curr_idB; curr_idB = (st+ed)/2;}
        		}while(ed>st+1);
        
        		//find B[bk-1] in A[0...ak-1], return new_id,new_m for A[]
        		st=0;ed=ak-1;
        		int curr_idA = (st+ed)/2;
        		do
        		{
        			if(A[curr_idA]==B[bk-1])
        				break;
        			else if(A[curr_idA]>B[bk-1])
        			{ed = curr_idA; curr_idA = (st+ed)/2;}
        			else
        			{st = curr_idA+1; curr_idA = (st+ed)/2;}
        		}while(ed>st+1);
        
        		//throw away curr_idA elements in A and bk-1 elements in B
        		//return the (k-curr_idA-(bk-1))th in A[],B[]
        		//if n=1 then we can't throw away B[bk-1]
        		return findKthSortedArrays(&A[curr_idA],ak-curr_idA,
        								   &B[bk],curr_idB-bk+1,
        								   k-curr_idA-bk);
        	}
        	else//(A[ak-1] < B[bk-1])
        	{
        		//find A[ak-1] in B[0...bk-1], return new_id,new_n for B[]
        		int st=0,ed=bk-1;
        		int curr_idB = (st+ed)/2;
        		
        		do{
        			if(B[curr_idB]==A[ak-1])
        				break;
        			else if(B[curr_idB]>A[ak-1])
        			{ed = curr_idB; curr_idB = (st+ed)/2;}
        			else
        			{st = curr_idB+1; curr_idB = (st+ed)/2;}
        		}while(ed>st+1);
        
        		//find B[bk-1] in A[ak-1...m-1], return new_id,new_m for A[]
        		st=ak;ed=m-1;
        		int curr_idA = (st+ed)/2;
        		do{
        			if(A[curr_idA]==B[bk-1])
        				break;
        			else if(A[curr_idA]>B[bk-1])
        			{ed = curr_idA; curr_idA = (st+ed)/2;}
        			else
        			{st = curr_idA+1; curr_idA = (st+ed)/2;}
        		}
        		while(ed>st+1);
        		
        		//throw away ak-1 elements in A and bk-1 elements in B
        		//return the (k-curr_idA-(bk-1))th in A[],B[]
        		return findKthSortedArrays(&A[ak],curr_idA-ak+1,
        								   &B[curr_idB],bk-curr_idB,
        								   k-curr_idB-ak);
        	}
        
        }
    

    Submission Result: Wrong Answer

    Input: [1,3,4,5,6], [2]

    Output: 4.00000

    Expected: 3.50000

    but when I ran my codes on my computer, I got 3.5 correctly...


  • 0
    S

    Could you please update your post with correct code format, explanation of algorithm, and comments in code? Thanks.


  • 0
    M
    This post is deleted!

  • 0
    S

    Hi @michaelhu, could you please repost a new question? Since this question is a bad sample, no explanation, no code comments, I will hide this one.


Log in to reply
 

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