My C code using hashtable, but failed in gigantic linear testcase


  • 0
    L

    It tests using a long linear array with about 30000 more elements, and said time limit exceeded. Could anybody give me a hint?

    typedef struct HashNode{
        int key;
        int val;
    }HashNode;
    
    typedef struct HashMap{
        int size; 
        HashNode **storage;
    }HashMap;
    
    HashNode *hashnode_create(int *nums, int numsSize){
        int i;
        HashNode *hashnode = (HashNode *)malloc(sizeof(HashNode) * numsSize);
        for(i=0; i<numsSize; i++){
            hashnode[i].key = i+1;
            hashnode[i].val = nums[i];
        }
        return hashnode;
    
    }
    
    int *twoSum(int *nums, int numsSize, int target){
        int i, j;
        int *res = malloc(sizeof(int) * 2);
       HashNode *hashnode = hashnode_create(nums, numsSize);
        for(i=0; i<numsSize; i++){
            for(j=numsSize-1; j>=0; j--){
    	    if(j == i){
    		    continue;
    	    }else{
    	    	if(target - nums[i] == nums[j]){
    		        res[0] = hashnode[i].key;
    		        res[1] = hashnode[j].key;
    		        return res;
    		    }
    	    }			
            }
        }
        printf("No result found!\n");
        
        return NULL;
    }

  • 1
    X

    Hi, likaikoplee,

    What you have here is not a hashtable even it was named so.

    This is a plain table with index "key" or (i+1) mapping to "val" or nums[i]. This table does not relieve the burden of O(n*n) complexity.

    To make a hashtable that may help, you need to make it map from nums[i] or (target-nums[i]) to index i or i-1 and you need a hash function that has O(1) complexity searching one item.


Log in to reply
 

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