Fastest C solution 6ms


  • 0
    bool getBit(unsigned char* c, int offset){
        int tmp = *c;
        tmp = tmp<<offset;
        tmp = tmp & 0x80; // 1000 0000
        return tmp==0x80;
    }
    
    void putBitTrue(unsigned char* c, int offset){
        switch(offset){
            case 0:
                *c = *c | 0x80; break; //1000 0000
            case 1:
                *c = *c | 0x40; break; //0100 0000
            case 2:
                *c = *c | 0x20; break; //0010 0000
            case 3:
                *c = *c | 0x10; break; //0001 0000
            case 4:
                *c = *c | 0x08; break; //0000 1000
            case 5:
                *c = *c | 0x04; break; //0000 0100
            case 6:
                *c = *c | 0x02; break; //0000 0010
            case 7:
                *c = *c | 0x01; break; //0000 0001
        }
    }
    
    bool containsDuplicate(int* nums, int numsSize) {
        if(!nums || numsSize<2) return false;
        unsigned int* un = (unsigned int*)nums;
        char* bigmap = malloc(0x0100000000/8); //Integer.MAX bits
        unsigned char* tmpPoint;
        int tmpOffset;
        int tmp;
        for(int i=0; i<numsSize; i++){
            tmpPoint = bigmap + un[i]/8;
            tmpOffset = un[i]%8;
            if(getBit(tmpPoint, tmpOffset)){
                free(bigmap);
                return true;
            } 
            else putBitTrue(tmpPoint, tmpOffset);
        }
        free(bigmap);
        return false;
    }
    

  • 0
    W

    thanks for sharing


Log in to reply
 

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