Make writing a habit together! This is the 13th day of my participation in the “Gold Digging Day New Plan · April More Text Challenge”. Click here for more details.

Topic describes

This is 380.o (1) time on LeetCode to insert, remove, and get random elements with moderate difficulty.

Tag: “data structure”, “hash table”

Implement RandomizedSet class:

  • RandomizedSet()Initialize theRandomizedSetobject
  • bool insert(int val)When the elementvalIf it does not exist, inserts the item into the collection and returnstrue; Otherwise, returnfalse.
  • bool remove(int val)When the elementvalExists, removes the item from the collection, and returnstrue; Otherwise, returnfalse.
  • int getRandom()Randomly returns an item from an existing collection (the test case ensures that at least one element is present in the collection when this method is called). Each element should have an equal probability of being returned.

You have to implement all of the functions of the class and meet an average time complexity of O(1)O(1)O(1) for each function.

Example:

Input [" RandomizedSet ", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2]. [], [1], [2], [] output [NULL, true, false, true, 2, true, false, 2] randomizedSet.insert(1); // Insert 1 into the set. Returning true indicates that 1 was successfully inserted. randomizedSet.remove(2); // Returns false to indicate that 2 does not exist in the collection. randomizedSet.insert(2); // Insert 2 into the set. Returns true. The collection now contains [1,2]. randomizedSet.getRandom(); // getRandom should randomly return 1 or 2. randomizedSet.remove(1); // Remove 1 from the collection, return true. The set now contains [2]. randomizedSet.insert(2); // 2 is already in the collection, so return false. randomizedSet.getRandom(); Since 2 is the only number in the set, getRandom always returns 2.Copy the code

Tip:


  • – 2 31 < = v a l < = 2 31 – 1 -2^{31} <= val <= 2^{31} – 1
  • Most callinsert,remove 和 getRandomfunction
    2 ∗   1 0 5 2 * 10 ^ 5     次
  • In the callgetRandomMethod exists at least one element in the data structure.

Hash table + delete swap

It is easy to think of “hash tables” for INSERT and remove operations to achieve O(1)O(1)O(1) complexity, but for getRandom operations, it is desirable to be able to return random subscripts within an array.

Combining the two, we can design the hash table to take the input parameter val as the key and the array subscript LOc as the value.

To ensure strictness
O ( 1 ) O(1) , we cannot “use reject sampling” and “add/remove elements at non-ending positions in an array”.

Therefore, we need to apply for a large enough array NUMS (data range 2∗1052* 10^52∗105), and use variable IDx to record which bit is currently used (i.e., subscripts within [0, IDx][0, IDx][0, IDX] are survival values).

For several types of operation logic:

  • insertAction: Use the hash table to determinevalIf yes, returnfasleOtherwise, add it tonumsTo updateidx, while updating the hash table;
  • removeAction: Use the hash table to determinevalDoes it exist? Returns if notfalse, otherwise from the hash table willvalDelete, and remove its locationnumsThe subscriptlocAnd thennums[idx]Assign values to thelocLocation, and updateidx(Meaning put the original inlocLocation of the element removed), while the update was originally locatedidxThe number of positions in the hash table is zeroloc(ifloc 与 idxEqual, indicating that the last element is deleted, this step can be skipped);
  • getRandomOperation: because we artificially ensured
    [ 0 . i d x ] [0, idx]     Are survival values, so directly in
    [ 0 . i d x + 1 ) [0, idx + 1)     Random can be carried out within the range.

Code:

class RandomizedSet {
    static int[] nums = new int[200010];
    Random random = new Random();
    Map<Integer, Integer> map = new HashMap<>();
    int idx = -1;
    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        nums[++idx] = val;
        map.put(val, idx);
        return true;
    }
    public boolean remove(int val) {
        if(! map.containsKey(val))return false;
        int loc = map.remove(val);
        if(loc ! = idx) map.put(nums[idx], loc); nums[loc] = nums[idx--];return true;
    }
    public int getRandom(a) {
        return nums[random.nextInt(idx + 1)]; }}Copy the code
  • Time complexity: all operations are O(1)O(1)O(1)
  • Space complexity: O(n)O(n)O(n)

The last

This is the no.380 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 questions on LeetCode as of the start date, some of which have lock questions. We will finish all the questions without lock first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.