8ms solution in C


  • 0
    R
    typedef struct hash_node
    {
        int value;
        int index;
        struct hash_node *next;
    } hash_node_t;
    
    
    bool containsNearbyDuplicate(int* nums, int numsSize, int k) {
        hash_node_t **table;
        table = calloc(numsSize, sizeof(hash_node_t));
        memset(table, 0, sizeof(hash_node_t) * numsSize );
        
        int i = 0;
        int key = 0;
        hash_node_t *node = NULL;
        hash_node_t *p = NULL;
        bool result = false;
        
        for (i = 0; (i < numsSize && result == false); i++)
        {
            key = abs(*nums) % numsSize;
            node = malloc(sizeof(hash_node_t));
            node->value = *nums;
            node->index = i;
            node->next = table[key];
            table[key] = node;
            p = table[key]->next;
            while(p)
            {
                if ((p->value == *nums) && ((i - p->index) <= k))
                {
                    result = true;
                    break;
                }
                p = p->next;
            }
            nums++;
        }
        
        for (i = 0; i < numsSize; i++)
        {
            while(table[i])
            {
                p = table[i]->next;
                free(table[i]);
                table[i] = p;
            }
        }
        free(table);
        
        return result;
    }

  • 0
    T

    Does the hash function key = abs(*nums) % numsSize assume there is no collision? What if there is, such as the array is [-99, 99]?


  • 0
    T

    My bad, I think your while loop handles the collision.


Log in to reply
 

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