Median of Two Sorted Arrays, local test for [1,1], [1,1] return 1.0000, but OJ says it return nan


  • 0
    C

    Input: [1,1], [1,1]
    Output: nan
    Expected: 1.00000

    The output in my local test is 1.00000, while the OJ says the output is nan. The following is my code. Is the code wrong?

    class Solution {
    public:
        double findMedianSortedArrays(int A[], int m, int B[], int n) {
            if(m==0 && n==0) {
                return -1;
            }
            if(m==0) {
                if(n%2==0){
                    return 1.0*(B[n/2]+B[n/2-1])/2;
                } else {
                    return B[n/2];
                }
            }
            if(n==0) {
                if(m%2==0){
                    return 1.0*(A[m/2]+A[m/2-1])/2;
                }else{
                    return A[m/2];
                }
            }
            if(m<n) {
                return middle(A, 0, m-1, B, 0, n-1);
            } else {
                return middle(B, 0, n-1, A, 0, m-1);
            }
        }
    
        double middle(int A[], int sa, int ea, int B[], int sb, int eb){
            //printf("%d,%d,%d,%d\n", sa, ea, sb, eb);
            //lenA <= lenB
            int lenA = ea-sa+1;
            int lenB = eb-sb+1;
            int ma=(sa+ea)/2; //smaller if lenA%2==1
            int mb=(sb+eb)/2;
    
            if (lenA==1 && lenB==1) {
                return 1.0*(A[ma]+B[mb])/2;
            }
    
            if (1 == lenA) {
                if (lenB%2==0) {
                    if(A[ma] > B[mb]) {
                        if(A[ma] < B[mb+1]) {
                            return A[ma];
                        }else {
                            return B[mb+1];
                        }
                    } else {
                        return B[mb];
                    }
                } else {
                    //lenB%2 != 0
                    if(A[ma] > B[mb]){
                        if(A[ma] < B[mb+1]) {
                            return 1.0*(A[ma]+B[mb])/2;
                        }else{
                            return 1.0*(B[mb]+B[mb+1])/2;
                        }
                    } else {
                        if(A[ma] > B[mb-1]) {
                            return 1.0*(A[ma]+B[mb])/2;
                        } else {
                            return 1.0*(B[mb]+B[mb-1])/2;
                        }
                    }
                }
            }
            if (A[ma] < B[mb]) {
                int subLen=ma-sa;
                if (subLen == 0) subLen = 1;
                middle(A, sa+subLen, ea, B, sb, eb-subLen);
            } else {
                int subLen=ea-ma;
                if (subLen == 0) subLen = 1;
                middle(A, sa, ea-subLen, B, sb+subLen, eb);
            }
        }
    };

  • 0
    S

    Median of Two Sorted Arrays, local test for [1,1], [1,1] return 1.0000, but OJ says it return 0.50000.

    HI, i encounter the similar problem as described above. Is there anyone has the same problem? Please help my out.


  • 0
    C

    similar problem here. What I have is input: [1], [1], output: 0.500000, expected output: 1.00000. Don't know why


  • 0
    C

    Firstly, in the cases that m == 0 (and n == 0), when n % 2 == 0 (m % 2 == 0), you should always return 1.0*(B[n/2]+B[n/2+1])/2; instead of 1.0*(B[n/2]+B[n/2-1])/2;
    Then, check out your index in your middle function, it is quite possible that you miss some corner cases.


Log in to reply
 

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