C solution beats 97%


  • 3
    S
    bool containsNearbyDuplicate(int* nums, int numsSize, int k) {
        if(numsSize ==0) return false;
        if(k>numsSize) k= k% numsSize;
        int i, min= INT_MAX, max = INT_MIN;
        for(i=0; i<numsSize; i++){
            min = min< nums[i]? min: nums[i];
            max = max> nums[i]? max: nums[i];
        }
        int *hash = malloc((max-min+1)* sizeof(int));
        memset(hash, -1, (max-min+1)*sizeof(int));
        for(i=0; i<numsSize; i++){
            if(hash[nums[i]-min] == -1){
                hash[nums[i]-min] = i;
            }
            else if((i-hash[nums[i]-min]) <= k){
                return true;
            }
            else{
                hash[nums[i]-min] = i;
            }
        }
        return false;
    }

  • 3
    F

    Doesn't seem to be a good idea.
    The max range of int on a modern machine is usually ~2^32 meaning that your code could take up to 2^(32-30) * 4 = 16 Gigabyte of memory. You could save some memory by using an array of bool (4G) or even std::bitset (0.5G) which, however, is still bad.


  • 0
    T

    Since C does not have a hash table lib function, you would have to write one (only specific to this problem, not generic) yourself with small hash table size that can handle collision.


  • 0
    F

    I understand and agree to what you said but I dont understand why you said it. I was just saying that the op's solution takes up too much memory.


  • 0
    T

    I actually totally agree with you. My comments are for original solution, not your comments.


  • 0
    V

    memory is not freed, not a qualified c programmer.


Log in to reply
 

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