12ms C language solution with in-house HashSet


  • 26
    N
    struct Node
    {
        int val;
        struct Node *next;
    };
    
    struct Set
    {
        int bucketSize;
        struct Node **table;
    };
    
    void initSet(struct Set *set, int bucketSize)
    {
        set->bucketSize = bucketSize;
        set->table = malloc(sizeof(struct Node*) * bucketSize);
        memset(set->table, 0, sizeof(struct Node*) * bucketSize);
    }
    
    bool addValue(struct Set *s, int val)
    {
        int idx = val > 0 ? val : -val;
        idx %= s->bucketSize;
        struct Node *ptr = s->table[idx];
        while(ptr != NULL)
        {
            if(ptr->val == val)
            {
                return false;
            }
        
            ptr = ptr->next;
        }
        ptr = malloc(sizeof(struct Node));
        ptr->val = val;
        ptr->next = s->table[idx];
        s->table[idx] = ptr;
        return true;
    }
    void releaseSet(struct Set *s)
    {
        struct Node *ptr, *tmp;
        for(int i = 0; i < s->bucketSize; ++i)
        {
            ptr = s->table[i];
            while(ptr != NULL)
            {
                tmp = ptr;
                ptr = ptr->next;
                free(tmp);
            }
        }
        free(s->table);
        s->table = NULL;
        s->bucketSize = 0;
    }
    bool containsDuplicate(int* nums, int numsSize) {
        if(numsSize < 2)
        {
            return false;
        }
        struct Set set;
        initSet(&set, numsSize / 2);
        for(int i = 0; i < numsSize; ++i)
        {
            if(!addValue(&set, nums[i]))
            {
                releaseSet(&set);
                return true;
            }
        }
        releaseSet(&set);
        return false;
    }

  • -31
    Y

    two lines answer in c++

    1. class Solution { public:
      bool containsDuplicate(vector<int>& nums) {
      set<int> iset(nums.cbegin(),nums.cend());
      return iset.size()<nums.size();
      } };

  • 1
    S

    Why is it "initSet(&set, numsSize / 2)" instead of "initSet(&set, numsSize)" ?


  • 0
    X

    Hi, similar question to @skipeco , could you please explain a little bit how to decide the bucketSize?

    Thanks so much


  • 1
    F

    said in 12ms C language solution with in-house HashSet:

    int idx = val > 0 ? val : -val;

    This is not good in case val = INT_MIN.


  • 0
    W

    my 6ms Solution

    static int table[1048576 / 256];

    bool containsDuplicate(int* nums, int numsSize) {
    //6ms, beat 100%

      int m = 16, n = numsSize;
      while(m < n){
          m <<= 1;
      }
      m <<= 1;
      memset(table, 0, m * sizeof(int));
      int *is = table, *ip = is, *ie = is + m;
      int zcount = 0;
      m --;
      int *ps = nums, *pe = ps + n, *p=ps;
      for(; p < pe; ++p){
          int *ip = is + (*p & m);
          for(; *ip != 0; ){
              if(*ip == *p){
                  return true;
              }
              if(++ip == ie){
                  ip = is;
              }
          }
          if(*p == 0 && zcount ++ >= 1){
              return true;
          }
          *ip = *p;
      }
      return false;
    

    }


Log in to reply
 

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