Constant time delete / find any element in array

Implement random sets

It's a force lock 380 topic 「 Constant time insertion 、 Delete and get random elements 」, Look at the title ：

Let's implement the following class ：

class RandomizedSet {
    
public:
    /**  If  val  It doesn't exist in the set , Insert and return  true, Otherwise go straight back to  false */
     bool insert(int val) {
    }
    
    /**  If  val  In the assembly , Delete and return to  true, Otherwise go straight back to  false */
    bool remove(int val) {
    }
    
    /**  Get an element randomly from a set with a medium probability  */
    int getRandom() {
    }
}

The difficulty lies in 2 spot ：

1. Insert , Delete , The time complexity of the three operations of randomly obtaining elements is O（1）
2. getRandom Method must return elements with equal probability

Let's analyze first ： For inserting , Delete , Find these operations , What kind of data structure is time complexity is O(1)？

HashSet It must be one, right . The underlying principle of hash sets is a large array , We map elements to an index through a hash function ; If you use zipper to resolve hash conflict , Then the index may be linked to a linked list or a red black tree .

So, for such a standard HashSet, Can you be in O(1) In time getRandom function ？

In fact, it can't be , Because based on the bottom implementation just mentioned , Elements are hashed functions 「 Dispersed 」 Into the entire array , Not to mention zippers and other mechanisms to solve hash conflicts , So I can't do O(1) Time 「 Equal probability 」 Random access to elements .

LinkedHashSet Just for HashSet Increased order , Still can not achieve our getRandom function , Because the bottom layer uses linked list structure to store elements , Can't be in O(1) Of the time to access an element .

Based on the above analysis , about getRandom Method , If you want to 「 Equal probability 」 And 「 stay O(1) Time for 」 Take out the elements , Be sure to satisfy ： The bottom layer is implemented with arrays , And the array must be compact .

therefore , If we want to O(1) Delete an element in the array at the time of val, You can swap this element to the end of the array first , And then again pop fall .

The exchange of two elements has to be done through the index, right , So we need a hash table valToIndex To record the index corresponding to each element value .

class RandomizedSet {
    
    //<val,index> Record that each element corresponds to  nums  Index in 
    private HashMap<Integer,Integer> valToIndex;
    //  Store the value of the element 
    private List<Integer> list;
    private Random random=new Random();
    public RandomizedSet() {
    
        valToIndex=new HashMap<>();
        list=new ArrayList<>();
    }
    
    public boolean insert(int val) {
    
        //  if  val  Already exists , No need to insert 
        if (valToIndex.containsKey(val)) return false;
        //  if  val  non-existent , Insert into  nums  The tail ,
        //  And record  val  The corresponding index value 
        valToIndex.put(val,list.size());
        list.add(val);
        return true;
    }
    
    public boolean remove(int val) {
    
        //  if  val  non-existent , No need to delete 
        if(!valToIndex.containsKey(val)) return false;
         //  To get the first  val  The index of 
        int removePo=valToIndex.get(val);
        int lastVal=list.get(list.size()-1);
        //  Change the index corresponding to the last element to  index
        valToIndex.put(lastVal,removePo);
        //  Place val Set to the last element 
        list.set(removePo,lastVal);
        // Delete last position 
        valToIndex.remove(val);
        list.remove(list.size()-1);
        return true;
    }
    
    public int getRandom() {
    
        return list.get(random.nextInt(list.size()));
    }
}

thus , This problem is solved , The complexity of each operation is O(1), And the probability of random extraction is equal .

Avoid random numbers on the blacklist

With the foreshadowing of the above question , Let's look at a more difficult topic , Force to buckle 710 topic 「 Random numbers in the blacklist 」

Subject requirements , stay pick Functions should be called as few as possible to generate random number function rand().

Ideas ： Or use map Store the elements in the blacklist and the corresponding mappings

class Solution {
    
    int size = 0;
    HashMap<Integer, Integer> map = new HashMap<>();
    public Solution(int n, int[] blacklist) {
    
        size = n - blacklist.length;
        //map Deposit blackList The elements in 
        for(int item : blacklist){
    
            map.put(item, -1);
        }

        int last = n - 1;
        for(int item : blacklist){
    
            // If you were in the back, you wouldn't move 
            if(item >= size){
    
                continue;
            }
            // Or the last one won't be there blacklist Position in 
            while(map.containsKey(last)){
    
                last--;
            }
            // Store the blacklist elements in this location 
            map.put(item, last);
            last--;
        }
    }
    
    public int pick() {
    
        int index = (int)(Math.random()*size);
         return map.getOrDefault(index, index);
    }
}