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

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

Random recommended