Why does my C++ code get Runtime Error? It uses the comparing-medians method.


  • 0
    K

    The runtime error of my code is on the test case nums1 = [1,1] and nums2 = [1,1] (the answer should be (1+1)/2 = 1). My code uses the idea of comparing the medians of the two arrays, in the way of binary search. Although it works by my hand-calculating, please help me look at it.

    Thanks a lot.

    class Solution {
    public:

    double FM(vector<int>& A, int m, vector<int>& B, int n, int k)  {
        // find the median of sorted arrays A and B, by comparing their own medians
         
        if (m > n)    return FM(B, n, A, m, k); // if array A is longer than array B, swap them
    
        if (m == 0) return B[k-1];  // if A is empty then B[k-1] is the median of A and B
        if (k == 1)                 // if k = 1 then the median is the min of A[0] and B[0]
            if (A[0] < B[0])
                return A[0];
            else
                return B[0];
    
        int pa;
        if (k/2 < m)
            pa = k/2;
        else
            pa = m;
    
        int pb = k - pa;
    
        if (A[pa-1] <= B[pb-1])     // if the median of A <= the median of B
        {
            vector<int> AA;
            int i;
            
            for (i = pa; i < m; i ++)
                AA[i-pa] = A[i];
            return FM(AA, m-pa, B, n, k-pa);    // eliminate A's elements before its median
        }
    
        vector<int> BB;             // otherwise, if the median of A > the median of B
        int j;
        
        for (j = pb; j < n; j ++)
            BB[j-pb] = B[j];
        return FM(A, m, BB, n-pb, k-pb);        // eliminate B's elements before its median
    
    }
    
     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        
        int m = nums1.size();
        int n = nums2.size();
        int total;
        double median;
        
        total = m + n;
        
        if (total % 2 == 1)
            median = FM(nums1, m, nums2, n, total/2 + 1);
        else
            median = ( FM(nums1, m, nums2, n, total/2) + FM(nums1, m, nums2, n, total/2 + 1) ) / 2;
            
        return median;
    
    }
    

    };


Log in to reply
 

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