# Introduction to the algorithm "hash table" medium 03 - leetcode 380. O (1) time insertion, deletion and acquisition of random elements

2021-08-27 09:05:46

No food , Water does not drink , Questions must be brushed

C Language free animation tutorial , Punch in with me ！

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 ！

# One 、 subject

## 1、 Title Description

Design a support in average Time complexity O ( 1 ) O(1) Next , Data structure to do the following .
insert(val)： When element v a l val When there is no , Insert the item into the collection .
remove(val)： Elements v a l 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); */


# 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 ) 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 ) O(1) , in total n n Enumeration of numbers , The time complexity is O ( n ) O(n) .

## 3、 Code details

/********************  Hashtable   Open addressing  ********************/
#define maxn (1<<17)
#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;
}
}

return key & mask;        //  Division and remainder
}

Boolean HashSearchKey(HashTable *ht, DataType key, int *addr) {

return 0;                    //  An empty slot was encountered , It means that we didn't find , return  0
}

return 0;                    //  I looked around and didn't find , Circulated
}
}
return 1;
}

int HashInsert(HashTable *ht, DataType key) {

if ( HashSearchKey(ht, key, &retaddr ) ) {

}
}

int HashRemove(HashTable *ht, DataType key) {

if ( !HashSearchKey(ht, key, &addr ) ) {

return NULLKEY;
}
}

typedef struct {

HashTable ht;
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) {

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) {

addr = HashRemove( &obj->ht, val );
-- 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 ) (1) Hash table address to array subscript mapping ;
• ( 2 ) (2) Mapping of array subscript to hash table address ;
• ( 3 ) (3) Initialization array length is 0;
• ( 4 ) − ( 5 ) (4) - (5) In the process of inserting data , Simultaneous recording Hash table address and Mapping of array subscripts ;
• ( 6 ) − ( 8 ) (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 ) 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 ) O(1) , But doing so will change the order of the original array , You can do this if you don't require much order .