Hash table: the time complexity of insert, delete and random access is O (1)

subject

https://leetcode-cn.com/problems/FortPu/

Their thinking

See the time complexity O(1) You can think of arrays or hash tables .
The special situation here needs to be considered getRandom function , And return a random number with the same probability . So to achieve this goal , Can only return from the array , And the array has an index .

So the data structure we can design for this topic is ：
Hashtable ： The element to be modified is key, The index of the element is used as value.
Array ： Used to hold elements , And the array index can be used to generate a random number , You can return a number with a random number as the index of the array .

How to use time complexity from an array O（1） To delete an element ？

The most error prone place here is to delete a number .
Delete a number from the array , You need to traverse the array once , To find the deleted number , This time complexity is O(n); So we have to use another technique ：
First, the last number in the list and the number to be deleted （ We have used the hash table as the subscript value Save ） In exchange for . After exchanging , You can delete the last number of the list each time , In this way, the time complexity reaches O(1);

The specific code is as follows ：

Code

class RandomizedSet {
    

    // Hash table can be deleted , Inquire about O（1） Time complexity .
    Map<Integer, Integer> numToLocation = null;

    // Want to generate a random number with the same probability , You need a list index , The hash table does not have an index , We have to do this with arrays .
    //Nums Save values inside .  and HashMap Save the index with the value of .
    ArrayList<Integer> nums = null;
    /** Initialize your data structure here. */
    public RandomizedSet() {
    
        numToLocation = new HashMap<>();
        nums = new ArrayList<>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
    
        if(numToLocation.containsKey(val)){
    
            return false;
        }

        numToLocation.put(val, nums.size());
        nums.add(val);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
    
        if(!numToLocation.containsKey(val)) {
    
            return false;
        }
        int location = numToLocation.get(val);
        numToLocation.put(nums.get(nums.size() - 1), location);
        numToLocation.remove(val);
        nums.set(location, nums.get(nums.size() - 1));
        nums.remove(nums.size() - 1);
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
    
       Random random = new Random();
       int key = random.nextInt(nums.size());
       return nums.get(key);
    }
}

/** * Your RandomizedSet object will be instantiated and called as such: * RandomizedSet obj = new RandomizedSet(); * boolean param_1 = obj.insert(val); * boolean param_2 = obj.remove(val); * int param_3 = obj.getRandom(); */

summary

This topic examines the properties of hash tables and arrays , Time complexity O（1）. At the same time, how to delete a number of the array in combination with the hash table , And the time complexity O（1）.