> For the complete documentation index, see [llms.txt](https://leetcodebook-1.gitbook.io/top-interview-150/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcodebook-1.gitbook.io/top-interview-150/array-string/insert-delete-getrandom-o1.md).

# O(1)时间插入、删除和获取随机元素

题目链接: <https://leetcode.cn/problems/insert-delete-getrandom-o1>

## 解题思路：

1. 插入、删除、读取操作都需要在O(1)的时间内实现，所以直接用链表不合适，直接用数组也不合适
2. 可以采用切片+哈希表的方式进行实现
3. 通过切片能实现O(1)时间的插入以及随机读取，再通过哈希表记录每个元素的位置，在删除的时候直接选择元素覆盖缩减切片即可

```go
type RandomizedSet struct {
    data []int
    idxMap map[int]int
}


func Constructor() RandomizedSet {
    return RandomizedSet{
        data:[]int{},
        idxMap: map[int]int{},
    }
}


func (this *RandomizedSet) Insert(val int) bool {
    if _,ok:=this.idxMap[val];ok{
        return false
    }
    // 记录元素插入的位置
    this.idxMap[val]=len(this.data)
    this.data = append(this.data,val)
    return true
}


func (this *RandomizedSet) Remove(val int) bool {
    id,ok:=this.idxMap[val]
    if !ok{
        return false
    }
    last:=len(this.data)-1
    // 覆盖元素
    this.data[id]=this.data[last]
    // 修正最后一个元素的位置记录
    this.idxMap[this.data[id]] = id
    // 缩减切片
    this.data=this.data[:last]
    // 删除哈希表中的位置记录
    delete(this.idxMap,val)
    return true
}


func (this *RandomizedSet) GetRandom() int {
    return this.data[rand.Intn(len(this.data))]
}


/**
 * Your RandomizedSet object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Insert(val);
 * param_2 := obj.Remove(val);
 * param_3 := obj.GetRandom();
 */
```

## 复杂度分析一

* **时间复杂度：** 因此时间复杂度为 $$O(1)$$
* **空间复杂度：** 空间复杂度为 $$O(n)$$，其中 $$n$$ 是数组 $$输入数据的长度$$ 的长度


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

```
GET https://leetcodebook-1.gitbook.io/top-interview-150/array-string/insert-delete-getrandom-o1.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.