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

  • 0

    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 {

    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];
                return B[0];
        int pa;
        if (k/2 < m)
            pa = k/2;
            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);
            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.