I introduction

Design a data structure that supports the following operations under the average time complexity O(1).

Note: duplicate elements are allowed.

The collection contains the following three functions:

A.insert(val): inserts the element val into the collection.

B.remove(val): removes a val from the collection when it exists.

C.getRandom: get an element randomly from an existing collection. The probability that each element is returned should be linearly related to its number in the set.

Collection function example:

II realization

The set type is defined as RanomizedSet, which implements the above three methods: inserting elements, removing elements and randomly obtaining elements linearly related to the number of elements, and the time complexity is O(1). Here, the list is used to save the set elements, and dict is used to judge whether the elements exist. Therefore, although the time complexity of the above operations of the data structure is O(1), the space complexity also increases.

#!/usr/bin/python
# -*- coding: UTF-8 -*-

from random import choice


class RandomizedSet:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.dict = {}
        self.list = []

    def insert(self, val: int) -> bool:
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        """
        self.list.append(val)
        if val in self.dict:
            return False
        self.dict[val] = len(self.list) - 1
        return True

    def remove(self, val: int) -> bool:
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        """
        if val in self.dict:
            last_element, idx = self.list[-1], self.dict[val]
            self.list[idx], self.dict[last_element] = last_element, idx
            self.list.pop()
            del self.dict[val]
            return True
        return False

    def getRandom(self) -> int:
        """
        Get a random element from the set.
        """
        return choice(self.list

III Explain in detail

1.insert(val)

def insert(self, val: int) -> bool:
    """
    Inserts a value to the set. Returns true if the set did not already contain the specified element.
    """
    self.list.append(val)
    if val in self.dict:
        return False
    self.dict[val] = len(self.list) - 1
    return True

Insert elements into the collection. Since the requirement mentions that duplicate elements are allowed, the List is executed at the beginning here Append adds elements. There is a problem with the code given in the original title, so duplicate elements cannot be added. After adding a new element val to the List, store the corresponding position of val in the List. Here, dict is used to ensure that only one position of an element is saved. The return value is determined by dict. If dict exists, it returns False; otherwise, it returns True.

2.remove(val)

def remove(self, val: int) -> bool:
    """
    Removes a value from the set. Returns true if the set contained the specified element.
    """
    if val in self.dict:
        last_element, idx = self.list[-1], self.dict[val]
        self.list[idx], self.dict[last_element] = last_element, idx
        self.list.pop()
        del self.dict[val]
        return True
    return False

Remove the elements from the elements. This is the most complex part of the collection (actually not bad). The idea here is similar to bubble sorting.

A. Gets the value of the last element and the index of the value to delete

last_element, idx = self.list[-1], self.dict[val]

B. Delete the element at the value position, replace it with the last value in the list, and modify its index position in dict

self.list[idx], self.dict[last_element] = last_element, idx

C. Delete the value

In the previous step, modifying the value at list idx has actually deleted the val element. This step is mainly to update the data structure, pop reduce the length of the list and delete the redundant indexes in dict.

D. Return value

Contains elements and returns True when removed, otherwise returns False.

3.getRandom(val)

Here, the choice function comes from the random library and needs to be introduced from random import choice. If you want to implement it yourself, it is also very simple. You only need to randomly [0, len(list)-1] numbers and take values from the list. The probability of random to each index is 1/n, and n is the length of the list, so p(val) = 1/n * num, Num is the number of this number in the set, Therefore, the probability of p(val) satisfaction is linearly related to its number in the set.

def getRandom(self) -> int:
    """
    Get a random element from the set.
    """
    return choice(self.list)