current position:Home>Introduction to the algorithm "hash table" medium 03 - leetcode 380. O (1) time insertion, deletion and acquisition of random elements
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 【Where do heroes come out】
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 》
List of articles
One 、 subject
1、 Title Description
Design a support in average Time complexity O ( 1 ) O(1) O(1) Next , Data structure to do the following .
insert(val)
: When element v a l val val When there is no , Insert the item into the collection .
remove(val)
: Elements v a l val 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 ) (1) (1) 380. O(1) Time insertion 、 Delete and get random elements
( 2 ) (2) (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 ) 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) O(1), in total n n n Enumeration of numbers , The time complexity is O ( n ) O(n) 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 ) (1) (1) Hash table address to array subscript mapping ;
- ( 2 ) (2) (2) Mapping of array subscript to hash table address ;
- ( 3 ) (3) (3) Initialization array length is 0;
- ( 4 ) − ( 5 ) (4) - (5) (4)−(5) In the process of inserting data , Simultaneous recording Hash table address and Mapping of array subscripts ;
- ( 6 ) − ( 8 ) (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) 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) O(1), But doing so will change the order of the original array , You can do this if you don't require much order .
copyright notice
author[Where do heroes come out],Please bring the original link to reprint, thank you.
https://en.qdmana.com/2021/08/20210827090545127b.html
The sidebar is recommended
- Crazy blessing! Tencent boss's "million JVM learning notes", real topic of Huawei Java interview 2020-2021
- JS JavaScript how to get the subscript of a value in the array
- How to implement injection in vuex source code?
- JQuery operation select (value, setting, selected)
- One line of code teaches you how to advertise on Tanabata Valentine's Day - Animation 3D photo album (music + text) HTML + CSS + JavaScript
- An article disassembles the pyramid architecture behind the gamefi outbreak
- BEM - a front-end CSS naming methodology
- [vue3] encapsulate custom global plug-ins
- Error using swiper plug-in in Vue
- Another ruthless character fell by 40000, which was "more beautiful" than Passat and maiteng, and didn't lose BMW
guess what you like
-
Huang Lei basks in Zhang Yixing's album, and the relationship between teachers and apprentices is no less than that in the past. Netizens envy Huang Lei
-
He was cheated by Wang Xiaofei and Li Chengxuan successively. Is an Yixuan a blessed daughter and not a blessed home?
-
Zhou Shen sang the theme song of the film "summer friends and sunny days" in mainland China. Netizen: endless aftertaste
-
Pink is Wangyuan online! Back to the peak! The new hairstyle is creamy and sassy
-
Front end interview daily 3 + 1 - day 858
-
Spring Webflux tutorial: how to build reactive web applications
-
[golang] walk into go language lesson 24 TCP high-level operation
-
August 23, 2021 Daily: less than three years after its establishment, Google dissolved the health department
-
The female doctor of Southeast University is no less beautiful than the female star. She has been married four times, and her personal experience has been controversial
-
There are many potential safety hazards in Chinese restaurant. The top of the program recording shed collapses, and the artist will fall down if he is careless
Random recommended
- Anti Mafia storm: He Yun's helpless son, Sun Xing, is destined to be caught by his dry son
- Introduction to flex flexible layout in CSS -- learning notes
- CSS learning notes - Flex layout (Ruan Yifeng tutorial summary)
- Today, let's talk about the arrow function of ES6
- Some thoughts on small program development
- Talk about mobile terminal adaptation
- Unwilling to cooperate with Wang Yibo again, Zhao Liying's fans went on a collective strike and made a public apology in less than a day
- JS function scope, closure, let, const
- Zheng Shuang's 30th birthday is deserted. Chen Jia has been sending blessings for ten years. Is it really just forgetting to make friends?
- Unveil the mystery of ascension
- Asynchronous solution async await
- Analysis and expansion of Vue infinite scroll source code
- Compression webpack plugin first screen loading optimization
- Specific usage of vue3 video play plug-in
- "The story of huiyeji" -- people are always greedy, and fairies should be spotless!
- Installing Vue devtool for chrome and Firefox
- Basic usage of JS object
- 1. JavaScript variable promotion mechanism
- Two easy-to-use animation JS that make the page move
- Front end Engineering - scaffold
- Java SQL Server intelligent fixed asset management, back end + front end + mobile end
- Mediator pattern of JavaScript Design Pattern
- Array de duplication problem solution - Nan recognition problem
- New choice for app development: building mobile applications using Vue native
- New gs8 Chengdu auto show announces interior Toyota technology blessing
- Vieira officially terminated his contract and left the team. The national security club sent blessings to him
- Less than 200000 to buy a Ford RV? 2.0T gasoline / diesel power, horizontal bed / longitudinal bed layout can be selected
- How does "heart 4" come to an end? Pinhole was boycotted by the brand, Ma Dong deleted the bad comments, and no one blessed him
- We are fearless in epidemic prevention and control -- pay tribute to the front-line workers of epidemic prevention!
- Front end, netty framework tutorial
- Xiaomi 11 | miui12.5 | android11 solves the problem that the httpcanary certificate cannot be installed
- The wireless charging of SAIC Roewe rx5 plus is so easy to use!
- Upload and preview pictures with JavaScript, and summarize the most complete mybatis core configuration file
- [25] typescript
- CSS transform Complete Guide (Second Edition) flight.archives 007
- Ajax foundation - HTTP foundation of interview essential knowledge
- Cloud lesson | explain in detail how Huawei cloud exclusive load balancing charges
- Decorator pattern of JavaScript Design Pattern
- [JS] 10. Closure application (loop processing)
- Left hand IRR, right hand NPV, master the password of getting rich