TLE code, please help me!


  • 0
    C

    I keep get the TLE at the big case, but i thought my code was
    O(log(m+n)), here is my solution

    class Solution {
    public:
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            int len1=nums1.size();
            int len2=nums2.size();
            
            if(len1==1&&len2==1)
                return (nums1[0]+nums2[0])/2.0;
            if(len1==0)
                if(len2%2==0)
                    return (nums2[len2/2]+nums2[len2/2-1])/2.0;
                else
                    return nums2[len2/2];
            if(len2==0)
                if(len1%2==0)
                    return (nums1[len1/2]+nums1[len1/2-1])/2.0;
                else
                    return nums1[len1/2];
           
            
            int target=(len1+len2)/2;
            int current1=min(target/2-1,len1-1);
            int current2=min(target/2-1,len2-1);
            int take1=-1;
            int take2=-1;
            //int tim=0;
            int count=take1+take2+2;
            while(count!=target)
            {
                //tim++;
               
                if(nums1[current1]>nums2[current2])
                {
                    take2=current2;
                    
                    current2=min(current2+(target-count+1)/2,len2-1);
                    count=take1+take2+2;
                    if(take2==len2-1)
                    {
                        take1=take1+target-count;
                        break;
                    }
                    if(target-count>(len2-1-take2))
                    {
                        take1=take1+target-count-(len2-1-take2);
                        if(take1==len1-1)
                        {
                            take2=take2+target-count;
                            break;
                        }
                    }
                    current1=max(current1-(target-count+1)/2,take1+1);
                }
                else 
                {
                    take1=current1;
                    count=take1+take2+2;
                    current1=min(current1+(target-count+1)/2,len1-1);
                    
                    if(take1==len1-1)
                    {
                        take2=take2+target-count;
                        break;
                    }
                    if(target-count>(len1-1-take1))
                    {
                        take2=take2+target-count-(len1-1-take1);
                        if(take2==len2-1)
                        {
                            take1=take1+target-count;
                            break;
                        }
                    }
                    
                    current2=max(current2-(target-count+1)/2,take2+1);
                }
                 count=take1+take2+2;
                 //cout<<take1<<endl;
                 //cout<<take2<<endl;
            }
            //cout<<take1<<endl;
            //cout<<take2<<endl;
           
            if((len1+len2)%2==0)
            {
                double g;
                if(take1!=-1&&take2!=-1)
                    g=max(nums1[take1],nums2[take2]);
                else
                    if(take1==-1)
                        g=nums2[take2];
                    else
                        g=nums1[take1];
                double k;
                if(take1!=len1-1&&take2!=len2-1)
                    k=min(nums1[take1+1],nums2[take2+1]);
                else
                {
                    if(take1==len1-1)
                        k=nums2[take2+1];
                    else
                        k=nums1[take1+1];
                }
                return (g+k)/2;
            }
            else
            {
                if(take1!=len1-1&&take2!=len2-1)
                    return min(nums1[min(take1+1,len1-1)],nums2[min(take2+1,len2-1)]);
                else
                {
                    if(take1==len1-1)
                        return nums2[take2+1];
                    else
                        return nums1[take1+1];
                }
            }
        }
    };
    
    

    can anyone help with me, thank you a lot!!


Log in to reply
 

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