Why always hash? The truely O(1)


  • 0
    8

    Change echo value into binary, and regard it as a string.
    We can storage it with a Trie.
    And we change a little and fit duplicates allowed version.

    typedef struct RandomizedSetNode_S {
        int iCnt;
        struct RandomizedSetNode_S* apstSucc[2];
    } RandomizedSetNode;
    
    typedef struct {
        RandomizedSetNode *head;
    } RandomizedSet;
    
    /** Initialize your data structure here. */
    RandomizedSetNode* randomizedSetNodeCreate() {
        RandomizedSetNode *pstRet = malloc(sizeof(RandomizedSetNode));
        pstRet->iCnt = 0;
        pstRet->apstSucc[0] = NULL;
        pstRet->apstSucc[1] = NULL;
        return pstRet;
    }
    
    void randomizedSetNodeFree(RandomizedSetNode* obj) {
        if (obj->apstSucc[0] != NULL) {
            randomizedSetNodeFree(obj->apstSucc[0]);
        }
        if (obj->apstSucc[1] != NULL) {
            randomizedSetNodeFree(obj->apstSucc[1]);
        }
        free(obj);
    }
    
    /** Initialize your data structure here. */
    RandomizedSet* randomizedSetCreate() {
        RandomizedSet *pstRet = malloc(sizeof(RandomizedSet));
        pstRet->head = randomizedSetNodeCreate();
        return pstRet;
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool randomizedSetInsert(RandomizedSet* obj, int val) {
        RandomizedSetNode *pstNode = obj->head;
        for (int iPos = 0; iPos < 32; iPos++) {
            int iBit = (val >> iPos) & 1;
            if (pstNode == NULL) {
                break;
            }
            pstNode = pstNode->apstSucc[iBit];
        }
        if (pstNode != NULL) {
            return false;
        }
        pstNode = obj->head;
        pstNode->iCnt++;
        for (int iPos = 0; iPos < 32; iPos++) {
            int iBit = (val >> iPos) & 1;
            if (pstNode->apstSucc[iBit] == NULL) {
                pstNode->apstSucc[iBit] = randomizedSetNodeCreate();
            }
            pstNode = pstNode->apstSucc[iBit];
            pstNode->iCnt++;
        }
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool randomizedSetRemove(RandomizedSet* obj, int val) {
        RandomizedSetNode *pstNode = obj->head;
        for (int iPos = 0; iPos < 32; iPos++) {
            int iBit = (val >> iPos) & 1;
            if (pstNode->apstSucc[iBit] == NULL) {
                return false;
            }
            pstNode = pstNode->apstSucc[iBit];
        }
        pstNode = obj->head;
        pstNode->iCnt--;
        for (int iPos = 0; iPos < 32; iPos++) {
            int iBit = (val >> iPos) & 1;
            if (pstNode->apstSucc[iBit]->iCnt == 1) {
                randomizedSetNodeFree(pstNode->apstSucc[iBit]);
                pstNode->apstSucc[iBit] = NULL;
                break;
            }
            pstNode = pstNode->apstSucc[iBit];
            pstNode->iCnt--;
        }
        return true;
    }
    
    /** Get a random element from the set. */
    int randomizedSetGetRandom(RandomizedSet* obj) {
        RandomizedSetNode *pstNode = obj->head;
        int iZeroCnt, iOneCnt;
        int iAnswer = 0, iBit;
        for (int iPos = 0; iPos < 32; iPos++) {
            iZeroCnt = 0;
            iOneCnt = 0;
            if (pstNode->apstSucc[0] != NULL) {
                iZeroCnt = pstNode->apstSucc[0]->iCnt;
            }
            if (pstNode->apstSucc[1] != NULL) {
                iOneCnt = pstNode->apstSucc[1]->iCnt;
            }
            assert(iZeroCnt + iOneCnt > 0);
            if ((rand() + 1.) / (RAND_MAX + 2.) < iZeroCnt * 1. / (iZeroCnt + iOneCnt)) {
                iBit = 0;
            } else {
                iBit = 1;
            }
            assert(iBit == 1 || iZeroCnt > 0);
            assert(iBit == 0 || iOneCnt > 0);
            iAnswer |= iBit << iPos;
            pstNode = pstNode->apstSucc[iBit];
        }
        
        return iAnswer;
    }
    
    void randomizedSetFree(RandomizedSet* obj) {
        randomizedSetNodeFree(obj->head);
        free(obj);
    }
    

Log in to reply
 

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