# 380 insert delete getrandom O(1)

```java
class RandomizedSet {
    private Map<Integer, Integer> map;
    private List<Integer> list;
    public RandomizedSet() {
        map = new HashMap<>();
        list = new ArrayList<>();
    }
    
    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        list.add(val);
        map.put(val, list.size() - 1);
        return true;
    }
    
    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        int index = map.get(val);
        if (index == list.size() - 1) {
            map.remove(val);
            list.remove(index);
            return true;
        }
        map.remove(val);
        int tmp = list.get(list.size() - 1);
        list.remove(list.size() - 1);
        list.set(index, tmp);
        map.put(tmp, index);
        return true;
    }
    
    public int getRandom() {
        Random random = new Random();
        int index = random.nextInt(list.size());
        return list.get(index);
    }
}

/**
 * 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();
 */
```

注意如果你不care list里的顺序你是可以做到O(1) delete的，只需要把最后一个元素换到index的位置然后把最后一个元素删除掉，但是要注意如果index就是最后一个元素就直接删除，同时记得map里更新原本最后一个元素对应的index

注意random class的使用，nextInt的bound是non inclusive的


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hzhang.gitbook.io/leetcode-record/map-set/380-insert-delete-getrandom-o-1.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.