> For the complete documentation index, see [llms.txt](https://longxingtan.gitbook.io/mle-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://longxingtan.gitbook.io/mle-interview/01_leetcode/03_hash/380.-insert-delete-getrandom-o-1.md).

# 380. Insert Delete GetRandom O(1)

<https://leetcode.com/problems/insert-delete-getrandom-o1/>

## solution

> 要求: each function works in average O(1) time complexity

```python
class RandomizedSet:
    def __init__(self):
        self.list = []
        self.data_map = {}

    def insert(self, val: int) -> bool:
        if val in self.list:
            return False
        self.list.append(val)
        self.data_map[val] = len(self.list)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.data_map:
            return False
        last_element = self.list[-1]
        index_of_element = self.data_map[val]

        self.data_map[last_element] = index_of_element
        self.list[index_of_element] = last_element

        self.list[-1] = val
        self.list.pop()
        self.data_map.pop(val)
        return True

    def getRandom(self) -> int:
        return random.choice(self.list)
```

时间复杂度：O()\
空间复杂度：O()

```python
class RandomizedSet:
    def __init__(self):
        self.set = set()

    def insert(self, val: int) -> bool:
        if val in self.set:
            return False
        else:
            self.set.add(val)
            return True

    def remove(self, val: int) -> bool:
        if val in self.set:
            self.set.remove(val)
            return True
        return False

    def getRandom(self) -> int:
        # set无序，转为list需要创建index，时间复杂度O(n)
        return random.choice(list(self.set))
```

## follow up

[381. Insert Delete GetRandom O(1) - Duplicates allowed](https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/description/)

```python
# follow1: delete function with a twist that there can be duplicates as well
# follow2: Modify the map such that each unique element has equal probability of being returned. Ex: If values in map are [5,5,6,5,5] both 5 and 6 have 50% probability of being returned.

```