How to achieve 0ms with C?


  • 0
    T

    My O(n) solution takes 4ms. But there seems to be some 0ms submissions?


  • 0
    D

    calling malloc 60 (current number of test cases) times will for sure by itself take over 1ms on a reasonable machine. My guess is that 0ms were achieved in the past with fewer test cases.

    I have a 3ms solution that uses ghetto hash table/set sorta thing:

    #define HASH_SIZE 4096
    int hash(int val) {
        return val%HASH_SIZE;
    }
    
    void insert(int val, int *set, int *visited, int *order, int *size) {
        int h = hash(val);
        while(visited[h] && set[h]!=val)
            h = (h+1)%HASH_SIZE;
        if (!visited[h]) {
            order[*size] = val;
            (*size)++;
            set[h] = val;
            visited[h] = 1;
        }
    }
    
    bool inSet(int val, int *set, int *visited) {
        int h = hash(val);
        while(visited[h] && set[h]!=val)
            h = (h+1)%HASH_SIZE;
        return visited[h];
    }
    
    /**
     * Return an array of size *returnSize.
     * Note: The returned array must be malloced, assume caller calls free().
     */
    int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
        int nums1Set[HASH_SIZE];
        int visited1[HASH_SIZE]={0};
    
        int nums2Set[HASH_SIZE];
        int visited2[HASH_SIZE]={0};
        int order2[HASH_SIZE];
    
        for(int i=0; i<nums1Size; i++)
            insert(nums1[i], nums1Set, visited1, order2, returnSize);
        
        *returnSize=0;
        for(int i=0; i<nums2Size; i++)
            if(inSet(nums2[i], nums1Set, visited1))
                insert(nums2[i], nums2Set, visited2, order2, returnSize);
        
        int *ret = (int *)malloc(sizeof(int)*(*returnSize));
        for(int i=0; i<*returnSize; i++)
            ret[i]=order2[i];
            
        return ret;
    }

Log in to reply
 

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