12ms 83% O(n) time O(n) space with hand-built hash map in C


  • 0
    A

    The hash map uses open addressing and deals with collisions in the array.

    typedef enum state_t {
      FREE,BUSY
    } state_t;
    
    typedef struct elem_t {
      int key;
      int value;
      state_t state;
    } elem_t;
    
    typedef struct hashMap {
      int size;
      int pop;
      elem_t *table;
    } hashMap;
    
    void initHashMap(hashMap *H, int size){
      int i;
      if(!H){
        printf("Hash map pointer must not be null");
      }
      H->size=size;
      H->pop=0;
      H->table=malloc(size*sizeof(elem_t));
      for(i=0;i<size;i++){
        H->table[i].state=FREE;
        H->table[i].key=0;
        H->table[i].value=0;
      }
    }
    
    int hashFunc(uint32_t key, uint32_t size){
      int res = (int)((key*2654435761)>>16)%size;
      return res;
    }
    
    int insertHashMap(hashMap *H, int key, int value){
      int i=hashFunc(key,H->size);
      //same key?
      int counter=0;
      while(counter < H->size &&
            (H->table[i].state == BUSY && H->table[i].key != key )){
        i=(i+1) % H->size;
        counter++;
      }
      if(counter == H->size){
        return -1;
      }
      H->table[i].key=key;
      H->table[i].value=value;
      H->table[i].state=BUSY;
      H->pop++;
      return 1;
    }
    
    int queryHashMap(hashMap *H, int key, int *value){
      int i=hashFunc(key,H->size);
      int counter=0;
      while(counter < H->size &&
            H->table[i].state != FREE){
        if(H->table[i].state == BUSY && H->table[i].key == key ){
          *value = H->table[i].value;
          return 1;
        }
        counter++;
      }
      return 0;
    }
    
    int* twoSum(int* nums, int numsSize, int target) {
      int *res=NULL;
      int val;
      int i;
      int *numsPairs=malloc(numsSize*sizeof(int));
      hashMap H;
      initHashMap(&H,10*numsSize);
      for(i=0;i<numsSize;i++){
        insertHashMap(&H,nums[i],i);
      }
      for(i=0;i<H.size;i++){
        if(queryHashMap(&H,target-nums[i],&val) && val!=i){
          res=malloc(2*sizeof(  int ));
          res[0]=i;
          res[1]=val;
          return res;
        }
      }
      free(H.table);
      free(numsPairs);
      return res;
    }
    

Log in to reply
 

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