[Run Time Error] on big test case C++


  • 0
    M
    class Solution {
    public:
        int maximumGap(vector<int> &num) {
            if (num.size()<=2) return 0;
            
            unordered_set<int> pool;
            for (int i=0;i<num.size();pool.emplace(num[i++]));
            if (pool.size()==1) return 0;
            
            int maxNum = INT_MIN;
            int minNum = INT_MAX;
            for (auto it=pool.begin();it!=pool.end();it++){
                if ((*it)>maxNum) maxNum = *it;
                if ((*it)<minNum) minNum = *it;
            }
            
            const int bucket_size = (maxNum-minNum)/(pool.size()-1);
            const int bucket_num = 1+((maxNum-minNum)/bucket_size);
            
            vector<int> bucket_max(bucket_num,INT_MIN);
            vector<int> bucket_min(bucket_num,INT_MAX);
            
            for (auto it = pool.begin();it!=pool.end();it++){
                int loc = (*it-minNum)/(pool.size()-1);
                if ((*it)>bucket_max[loc]) bucket_max[loc] = *it;
                if ((*it)<bucket_min[loc]) bucket_min[loc] = *it;
            }
            
            int maxDiff = 0;
            
            for (int i=0;i<bucket_num-1;){
                int j = i+1;
                for (;j<bucket_num&&bucket_min[j]==INT_MAX;j++);
                if (j<bucket_num) maxDiff = max(maxDiff, bucket_min[j]-bucket_max[i]);
                i = j;
            }
            
            return maxDiff;
        }
    };
    

    Any idea?
    Run time error on:
    [12115,10639,2351,29639,31300,11245,16323,24899,8043,4076,17583,15872,19443,12887,5286,6836,31052,25648,17584,24599,13787,24727,12414,5098,26096,23020,25338,28472,4345,25144,27939,10716,3830,13001,7960,8003,10797,5917,22386,12403,2335,32514,23767,1868,29882,31738,30157,7950,20176,11748,13003,13852,19656,25305,7830,3328,19092,28245,18635,5806,18915,31639,24247,32269,29079,24394,18031,9395,8569,11364,28701,32496,28203,4175,20889,28943,6495,14919,16441,4568,23111,20995,7401,30298,2636,16791,1662,27367,2563,22169,1607,15711,29277,32386,27365,31922,26142,8792]


  • 0
    J

    First, change this line:

    int loc = (*it-minNum)/(pool.size()-1);
    

    to:

    int loc = (*it-minNum)/bucket_size;
    

    Last, if you do not rely on INT_MAX and INT_MIN, your logic will be more clear. I don't want to fix your messy code.


  • 1
    B

    I have get the same error during the submit, while it works well in the local.

    the most reason I find it's INT_MAX/INT_MIN, for the test data have INT_MAX in it, even I change it to LLONG_MAX, the same error I get.

    at last, I use -1 for the uninitialized slot, for the data must be "non-negative", and pass the test.

    but the reason while INT_MAX/LLONG_MAX will get Runtime Error in the online judge, I have no idea


Log in to reply
 

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