Runtime error, when inputing a long array


  • -2
    C
        class Solution {
    public:
    double searchKinTwo(int *array1, int *array2, int K, int l1, int r1, int l2, int r2)
    {
        //printf("%d %d %d %d %d\n",K,l1,r1,l2,r2);
        // first handle one of the array is empty
        if(r2<l2)
            return 1.0*array1[K-1];
        if(r1<l1)
            return 1.0*array2[K-1];
    
    
        if(K==1)
        {
            if(l1==-1) return array2[l2];
            if(l2==-1) return array1[l1];
            return array1[l1]>array2[l2]?array2[l2]:array1[l1];
        }
    
        if(r2==l2&&r1==l1)
        {
            if(array1[l1]<array2[l2])
                return K==1?array1[l1]:array2[l2];
            else
                return K==1?array2[l2]:array1[l1];
            //return (array1[l1]+array2[l2])/2.0;
        }
        int L1=-1, L2 = -1;
        int m1 = ((r1)+(l1))>>1;
        int m2 = ((r2)+(l2))>>1;
        L1 = m1-l1;
        L2 = m2-l2;
        int L;
    
        // need to compare median
        double med1,med2;
        if ((r1-l1+1)%2==1||l1==r1) med1 = array1[m1];
        else med1 = (array1[m1]+array1[m1+1])/2.0;
        if ((r2-l2+1)%2==1||l2==r2) med2 = array2[m2];
        else med2 = (array2[m2]+array2[m2+1])/2.0;
    
        if(med1<med2)
        {
            L = L1;
            return searchKinTwo(array1, array2, K-L-1, m1+1, r1, l2, m2);
        }
        else if (med1>med2)
        {
            L = L2;
            return searchKinTwo(array1, array2, K-L-1, l1, m1, m2+1, r2);
        }
        else
        {
            return med1;
        }
    }
    
    
    double findMedianSortedArrays(int A[], int m, int B[], int n)
    {
        int flag;
        if ((m+n)%2==0) flag = 0;
        else flag = 1;
    
        int K = (m+n)>>1;
    
        if(flag==1) K++;
    
        if(flag==0)
            return searchKinTwo(A,B,K,0,m-1,0,n-1);// + searchKinTwo(A,B,K+1,0,m-1,0,n-1))/2.0;
        else
            return searchKinTwo(A,B,K,0,m-1,0,n-1);
    }
        
    
    };
    

    Attached is my code, it meets runtime error, where could it be?


  • 0
    S

    Could you please describe your algorithm in some words?


  • 0
    C

    Hi, I recursively search the Kth element in two array by finding each array's median and delete those outside the range [median_low and median_high]


  • 0
    S

    Please just update your question post, do not reply in comment. Thanks!


  • 0
    Y

    My algorithm runs in O(m+n) and it is accepted. My idea is to find kth smallest number if array A and B are merged. Lets say A.length=m and B.length=n, here are 2 cases:

    1. if (m+n) is odd, find kth smallest number where k=(m+n)/2+1;

    2. if (m+n) is even, then the result is the average of two kth
      smallest numbers with k1=(m+n)/2 and k2=(m+n)/2+1 respectively

        public double findKthNumber(int[]A, int[]B, int m, int n, int k){
            int i=0;
            int j=0;
            int count=0;
            int result=0;
            while(i<m && j<n){
                if(A[i]<=B[j]){
                    result=A[i++];
                }
                else{
                    result=B[j++];
                }
                
                if(++count==k){
                    return result;
                }
            }
            if(i==m){
                return B[j+k-count-1];
            }
            else{
                return A[i+k-count-1];
            }
        }
    

Log in to reply
 

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