I solve in O(n) C++, I can't find any wrong in my code~


  • 0
    C

    I AC on my PC.
    But the OJ report the runtime error~

    I can't find any error in my code.
    Help~

    class Solution{
    

    public:
    struct Node{
    int val;
    Node* next;
    };

    typedef Node* node;
    
    int maximumGap(vector<int> &num) {
        int max,min;
        int length = (int)num.size();
        if (length < 2) {
            return 0;
        }
        vector<int>::iterator iter;
        min = num[0];
        max = num[0];
        for (iter = num.begin(); iter != num.end(); iter++) {
            if (min > *iter) {
                min = *iter;
                continue;
            }else if(max < *iter){
                max = *iter;
                continue;
            }
        }
        node n[length];
        for (int i = 0; i < length; i++) {
            n[i] = NULL;
        }
        float sub = ((float)(max-min)/(length-1));
        int number;
        node temp;
        for (iter = num.begin(); iter != num.end(); iter++) {
            number = (int)((*iter-min)/sub);
            temp = (node)malloc(sizeof(struct Node));
            temp->val = *iter;
            temp->next= n[number];
    

    // printf("%d\n",(int)sub);
    n[number] = temp;
    }
    int curmax = -1,nextmin = -1,nextmax = -1,maxSub = 0;
    temp = n[0];

        while (temp != NULL) {
            nextmax = nextmax > temp->val ? nextmax: temp->val;
            temp = temp->next;
        }
        
        for (int i = 0; i < length-1; i++) {
            curmax = nextmax;
            while (n[i+1] == NULL) {
                i++;
            }
            temp = n[i+1];
            nextmin = temp->val;
            nextmax = temp->val;
            while (temp != NULL) {
                nextmin = nextmin < temp->val?nextmin:temp->val;
                nextmax = nextmax > temp->val?nextmax:temp->val;
                temp = temp->next;
            }
    

    // printf("%d %d\n",nextmax,nextmin);
    maxSub = maxSub > (nextmin-curmax)?maxSub:(nextmin-curmax);
    }
    return maxSub;

    }
    

    };


  • 0
    C

    have you considered that max value of the array might equal min value of the array? 0 as a denominator definitely causes a runtime error.


  • 0
    C

    Thank you~ You are right~ but when i fix the bug, the code is also runtime error on OJ.

    I just want to know~ why the OJ can't show the test case which cause the runtime error problem.

    the case it gives is not the runtime error case.


Log in to reply
 

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