Why do i get a run time error


  • 0
    L
     double findMedianSortedArrays(int A[], int m, int B[], int n) {
         int i=m-1,j=n-1,len=m+n-1;
         if (m==0){
            if(j%2==0) return B[j/2];
            if(j%2==1) return (B[j/2]+B[(j+1)/2])/2;
         }
       //  if(len==0) return -1;
         while(i>=0&&j>=0){
             if(A[i]>=B[j]) A[len--]=A[i--];-
             else A[len--]=B[j--];
         }
         if(i==-1) {
             while(j>=0) A[len--]=B[j--];
         }
         len=m+n-1;
         if(len%2==0) return A[len/2];
         if(len%2==1) return (A[len/2]+A[(len+1)/2])/2;
     }
     };

  • 0
    M

    Unlike Merge Sorted Arrays, in this problem, the arrays really are that length. The variables are simply provided as a convenience in C++. Java and Python don't have them.

    Let A(m) and B(n) both be length 5. Then the values i and j are 4, and len is 9. Since both i and j are 4, they are greater than 0, so the loop is entered. At this point, it doesn't matter the values in A and B, since both use A[len--]. 9 is far beyond the limits of A, so the program crashes with a runtime error.

    For your algorithm, you need to create a third array of length m+n, then use that instead of A in the loops.

    However, your current solution takes O(n+m) time, and so violates

    The overall run time complexity should be O(log (m+n)).
    

    Even changing the algorithm to use the third array will likely fail due to TLE.


Log in to reply
 

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