Different output on local machine and OJ


  • 0

    I tried to implement a data structure by myself (a double linked ring)
    while I successfully get the right answer on my local machine, the OJ just report a runtime error. Could any one can help me figure it out? Thanks!

    1. I dont know why free will cause double free error (unless I comment those free)
    2. This program runs normally locally but only get a runtime error
    #include <stdio.h>
    #include <limits.h>
    #include <stdlib.h>
    
    /**
     * Return an array of size *returnSize.
     * Note: The returned array must be malloced, assume caller calls free().
     */
    /* Double linked ring buffer */
    typedef struct item {
        int val;
        struct item *next;
        struct item *prev;
    } item_t;
    
    item_t *items;
    int size;
    int head;
    item_t *median;
    
    double getMedian(void)
    {  
        if ( size == 2 ) {
            /* Only 2 number */
            return ((double)items[0].val + items[1].val) / 2.0;
        }
        if ( size % 2 == 0 ) {
          /* Even number */
          return ((double)median->val + median->next->val) / 2;
        } else {
          return median->val;
        } 
    }
    
    void slideWindow(int num)
    {
        item_t *curr = median;
        int i;
    
        for ( i = 0; i < size; i++ ) {
            printf("%d ", items[i].val);
        }
    
        printf("Median: %d, Add num: %d, head:%d, median addr%lx, head addr%lx\n", median->val, num, head, (unsigned long)median, (unsigned long)&items[head]);
    
        /* delete original, adjust median */
        head = (head + 1) % size;
        if ( items[head].val <= curr->val ) {
            median = curr->next;
        } 
        /* median will be the larger one now */
        curr = median;
        
        /* delete */
        items[head].next->prev = items[head].prev;
        items[head].prev->next = items[head].next;
       
        /* Insert new number */
        items[head].val = num;
        
        /* Reorder */
        if ( num == curr->val ) {
            /* Insert at right */
            /* so median->next will not be the next one to be deleted */
            items[head].prev = curr;
            items[head].next = curr->next;
            curr->next->prev = &items[head];
            curr->next = &items[head];
            return ;
        }
        
        if ( num < curr->val ) {
            while ( num < curr->val )
                curr = curr->prev;
            /* insert @right of current */
            items[head].prev = curr;
            items[head].next = curr->next;
            curr->next->prev = &items[head];
            curr->next = &items[head];
            median = median->prev;
            return ;
        }
        
        if ( num > curr-> val ) {
            while ( num > curr->val )
                curr = curr->next;
            /* insert @left of current */
            items[head].prev = curr->prev;
            items[head].next = curr;
            curr->prev->next = &items[head];
            curr->prev = &items[head];
            return ;
        }
    }
     
    double* medianSlidingWindow(int* nums, int numsSize, int k, int* returnSize)
    {
        double *ret;
        int i;
        item_t *min, *max, *tmp;
        ret = malloc(sizeof(double) * *returnSize);
        *returnSize = numsSize - k + 1;
        if ( k == 1 ) { /* Include numsSize is 1 */
            for ( i = 0; i < numsSize; i++ ) {
                ret[i] = (double)nums[i];
            }
            return ret;
        }
        
        /* init window */
        items = malloc(sizeof(item_t) * k);
        size = k;
        head = k - 1;
        
        min = malloc(sizeof(item_t));
        min->val = INT_MIN;
        min->prev = NULL;
        max = malloc(sizeof(item_t));
        min->next = max;
        min->next->val = INT_MAX;
        min->next->next = NULL;
        min->next->prev = min;
        tmp = min;
        
        for ( i = 0; i < k; i++ ) {
            tmp = min;
            while ( tmp != NULL && tmp->val <= nums[i] ) {
                tmp = tmp->next;
            }
            if ( tmp == NULL )
                /* Insert the INT_MAX */
                tmp = max;
    
            /* Insert @ left of tmp */
            items[i].val = nums[i];
            items[i].next = tmp;
            items[i].prev = tmp->prev;
            tmp->prev->next = &items[i];
            tmp->prev = &items[i];
        }
        tmp = min;
        for ( i = 0; i < (k + 1) / 2; i++ ) {
            tmp = tmp->next;
        }
        median = tmp;
        
        for ( i = 0; i < (*returnSize - 1); i++ ) {
            ret[i] = getMedian();
            slideWindow(nums[i + k]);
        }
        ret[*returnSize - 1] = getMedian();
        free(max);
        free(min);
        free(items);
        return ret;
    }
    
    int main(void)
    {
        //2147483647,1,2,3,4,5,6,7,2147483647
        // 2
        //1,3,-1,-3,5,3,6,7]
        //5
        //[1,3,-1,-3,5,3,6,7]
    //3
        int nums[] = {1, 3, -1, -3, 5, 3, 6, 7};
        int nums2[] = {INT_MAX, 1, 2, 3, 4, 5, 6, 7, INT_MAX};
        int returnSize;
        int i;
    
        printf("Input: ");
        for ( i = 0; i < 9; i++ ) {
            printf("%d ", nums[i]);
        }
        printf("\n");
        double *result = medianSlidingWindow(nums, 8, 3, &returnSize);
        for ( i = 0; i < returnSize; i++ ) {
            printf("%lf ", result[i]);
        }
        printf("\n");
    
        result = medianSlidingWindow(nums2, 9, 2, &returnSize);
    
        for ( i = 0; i < returnSize; i++ ) {
            printf("%lf ", result[i]);
        }
        printf("\n");
        free(result);
    
        return 0;
    }
    

  • 0

    Sorry for this stupid question. I found that these two lines are in wrong order.

        ret = malloc(sizeof(double) * *returnSize);
        *returnSize = numsSize - k + 1;
    

    It seems that I should not write code when I am sleepy. :)


Log in to reply
 

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