No food , Water does not drink , Questions must be brushed
C Language free animation tutorial , Punch in with me ！ 《 In broad daylight C Language 》
LeetCode Too difficult ？ First look at the simple question ！ 🧡《C Introduction to language 100 example 》🧡
Data structure is difficult ？ There is no the ！ 《 Figure out the data structure 》
LeetCode Too simple ？ The algorithm learns ！ 《 In the dead of night 》

One 、 subject

1、 Title Description

   Design a support in average Time complexity $O(1)$ Next , Data structure to do the following .
insert(val)： When element $val$ When there is no , Insert the item into the collection .
remove(val)： Elements $val$ In existence , Remove the item from the collection .
getRandom： Random return of an item in an existing collection . Each element should have the same probability to be returned .
   The sample input ： ["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"] [[],[1],[2],[2],[],[1],[2],[]]
   Sample output ： [null,true,false,true,2,true,false,2]

2、 Basic framework

• C Language version The basic framework code given is as follows ：

typedef struct {
    

} RandomizedSet;

/** Initialize your data structure here. */

RandomizedSet* randomizedSetCreate() {
    

}

/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
bool randomizedSetInsert(RandomizedSet* obj, int val) {
    

}

/** Removes a value from the set. Returns true if the set contained the specified element. */
bool randomizedSetRemove(RandomizedSet* obj, int val) {
    

}

/** Get a random element from the set. */
int randomizedSetGetRandom(RandomizedSet* obj) {
    

}

void randomizedSetFree(RandomizedSet* obj) {
    

}

/** * Your RandomizedSet struct will be instantiated and called as such: * RandomizedSet* obj = randomizedSetCreate(); * bool param_1 = randomizedSetInsert(obj, val); * bool param_2 = randomizedSetRemove(obj, val); * int param_3 = randomizedSetGetRandom(obj); * randomizedSetFree(obj); */

3、 Original link

$(1)$ 380. O(1) Time insertion 、 Delete and get random elements
$(2)$ The finger of the sword Offer II 030. Insert 、 Deletion and random access are O(1) The container of

Two 、 Problem solving report

1、 Thought analysis

  1） Maintain a hash table and two mapping arrays , These two arrays are Hash address to array subscript Mapping , and Array subscript to hash address Mapping ;
  2） The insert ： Perform a lookup on the hash table , If not found , Then insert , Two mapping arrays are updated during insertion ;
  3） Delete operation ： Perform a lookup on the hash table , If you find , Delete , During the deletion process, the mapping array is exchanged with the last element , Ensure that the deletion is $O(1)$ Of ;
  4） Random access ： Yes Array subscript to hash address This mapping array is randomly mapped , Get a hash address , Then go to the hash table, directly find the keyword through the subscript index, and then return ;

2、 Time complexity

• The average spreading complexity of hash table insertion and lookup is $O(1)$, in total $n$ Enumeration of numbers , The time complexity is $O(n)$.

3、 Code details

/********************  Hashtable   Open addressing  ********************/
#define maxn (1<<17)
#define mask (maxn-1)
#define DataType int
#define Boolean int
#define NULLKEY (1<<30) /*  Empty slot mark cannot be used -1, It will cause the normal value to be -1 The situation of */

typedef struct {
    
    DataType data[maxn];
}HashTable;

void HashInit(HashTable *ht) {
    
    int i;
    for(i = 0; i < maxn; ++i) {
    
        ht->data[i] = NULLKEY;
    }
}

int HashGetAddr(DataType key) {
    
    return key & mask;        //  Division and remainder 
}

Boolean HashSearchKey(HashTable *ht, DataType key, int *addr) {
    
    int startaddr = HashGetAddr(key);
    *addr = startaddr;
    while(ht->data[*addr] != key) {
    
        *addr = HashGetAddr(*addr + 1);
        if(ht->data[*addr] == NULLKEY) {
    
            return 0;                    //  An empty slot was encountered , It means that we didn't find , return  0
        }
        if(*addr == startaddr) {
    
            return 0;                    //  I looked around and didn't find , Circulated 
        }
    }
    return 1;
}

int HashInsert(HashTable *ht, DataType key) {
    
    int addr = HashGetAddr(key);
    int retaddr;
    if ( HashSearchKey(ht, key, &retaddr ) ) {
    
        return retaddr;
    } 
    while(ht->data[addr] != NULLKEY)
        addr = HashGetAddr(addr + 1);
    ht->data[addr] = key;
    return addr;
}

int HashRemove(HashTable *ht, DataType key) {
    
    int addr;
    if ( !HashSearchKey(ht, key, &addr ) ) {
    
        return NULLKEY;
    } 
    ht->data[addr] = NULLKEY;
    return addr;
}

/********************  Hashtable   Open addressing  ********************/

typedef struct {
    
    HashTable ht;
    int addr2pos[maxn];                       // (1)
    int pos2addr[maxn];                       // (2)
    int pos;
} RandomizedSet;

/** Initialize your data structure here. */

RandomizedSet* randomizedSetCreate() {
    
    RandomizedSet *rs = (RandomizedSet *)malloc( sizeof(RandomizedSet) );
    HashInit( &rs->ht );
    rs->pos = 0;                              // (3)
    return rs;
}

/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
bool randomizedSetInsert(RandomizedSet* obj, int val) {
    
    int addr;
    if (!HashSearchKey(&obj->ht, val, &addr)) {
    
        addr = HashInsert(&obj->ht, val);
        obj->addr2pos[ addr ] = obj->pos;         // (4)
        obj->pos2addr[ obj->pos++ ] = addr;       // (5)
        return true;
    }
    return false;
}

void swap(int *a, int *b) {
    
    int tmp = *a; 
    *a = *b;
    *b = tmp;
}

/** Removes a value from the set. Returns true if the set contained the specified element. */
bool randomizedSetRemove(RandomizedSet* obj, int val) {
    
    int addr, pre;
    if (HashSearchKey(&obj->ht, val, &addr)) {
    
        addr = HashRemove( &obj->ht, val );
        pre = obj->addr2pos[ addr ];                               // (6)
        obj->addr2pos[ obj->pos2addr[obj->pos-1] ] = pre;          // (7)
        swap( &obj->pos2addr[pre], &obj->pos2addr[obj->pos-1] );   // (8)
        -- obj->pos;
        return true;
    }
    return false;
}

/** Get a random element from the set. */
int randomizedSetGetRandom(RandomizedSet* obj) {
    
    return  obj->ht.data[ obj->pos2addr[ rand() % obj->pos ] ];
}

void randomizedSetFree(RandomizedSet* obj) {
    
    free(obj);
}

/** * Your RandomizedSet struct will be instantiated and called as such: * RandomizedSet* obj = randomizedSetCreate(); * bool param_1 = randomizedSetInsert(obj, val); * bool param_2 = randomizedSetRemove(obj, val); * int param_3 = randomizedSetGetRandom(obj); * randomizedSetFree(obj); */

• $(1)$ Hash table address to array subscript mapping ;
• $(2)$ Mapping of array subscript to hash table address ;
• $(3)$ Initialization array length is 0;
• $(4)-(5)$ In the process of inserting data , Simultaneous recording Hash table address and Mapping of array subscripts ;
• $(6)-(8)$ The element in the array that needs to be deleted , Swap with the last element of the array , In this way, you can delete $O(1)$ Of ;

3、 ... and 、 Little knowledge of this topic

   Delete data from an array , You can swap it with the last array element , Then, the array's size Minus one , This can do $O(1)$, But doing so will change the order of the original array , You can do this if you don't require much order .