Share my solution C++


  • 0
    I

    I really checked other solutions and I find some really good solutions. I used the same idea like most of people, but it has a little difference in shrink the search range in both arrays. I think my method take longer time in finding the position second sorted array. But anyway, just share it so you can avoid the same issue.

    class Solution {
    public:
        double findMedianSortedArrays(int A[], int m, int B[], int n) 
    	{
    		int nsum = m + n;
    		if ((nsum & 1) == 1)
    			return findKthNumber(A, 0, m, B, 0, n, (nsum/2)+1);
    		else
    			return (1.0*(findKthNumber(A, 0, m, B, 0, n, nsum/2)+findKthNumber(A, 0, m, B, 0, n, (nsum/2)+1)))/2;
        }
    
    private:
    	double findKthNumber(int A[], int nStartA, int nEndA, int B[], int nStartB, int nEndB, int k)
    	{
    		if (nEndA == nStartA)
    			return getNum(B, nStartB, k);
    		else if (nEndB == nStartB)
    			return getNum(A, nStartA, k);
    
    		int nHalfA = (nEndA - nStartA)/2;
    		int npos = searchPos(B, nStartB, nEndB, A[nStartA + nHalfA]);
    
    		int nDiff = npos + nHalfA + 1 - k;
    
    		if (nDiff == 0)
    			return A[nStartA + nHalfA];
    		else if (nDiff > 0)
    		{ 
    			return findKthNumber(A, nStartA, nStartA+nHalfA, B, nStartB, nStartB + npos, k);
    		}
    		else
    		{
    			return findKthNumber(A, nStartA + nHalfA + 1, nEndA, B, nStartB + npos, nEndB, k - nHalfA - npos - 1);
    		}
    	}
    
    	int getNum(int arr[], int nStart, int k)
    	{
    		return arr[nStart + k - 1];
    	}
    
    	int searchPos(int arr[], int nStart, int nEnd, int nElement)
    	{
    		int ntemp = nStart;
    		while (nEnd > nStart)
    		{
    			if (nElement >= arr[nStart + (nEnd-nStart)/2])
    			{
    				nStart += ((nEnd - nStart)/2 + 1);
    			}
    			else
    			{
    				nEnd = (nStart + (nEnd - nStart)/2);
    			}
    		}
    
    		return nStart - ntemp;
    	}
    };

Log in to reply
 

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