O(1) 插入、删除和随机访问
Insert Delete GetRandom O(1)
题目详情
问题：O(1) 插入、删除和随机访问
考察：数组、哈希表、数学
来源：DSA Prep / Citadel
链接：https://leetcode.com/problems/insert-delete-getrandom-o1
英文原题
Problem: Insert Delete GetRandom O(1)
Patterns: Array, Hash Table, Math
Recency: 6mo
Link: https://leetcode.com/problems/insert-delete-getrandom-o1
Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/
解析
思路：用数组存元素，用哈希表记录值到数组下标。删除时把待删元素和数组最后一个元素交换，再弹出末尾并更新下标；随机返回数组中的随机下标。
复杂度：insert/remove/getRandom 平均 O(1)，空间 O(n)。
英文解析
Approach: Store values in an array and a map from value to its array index. Removal swaps the target with the last element, updates the moved value’s index, and pops the array.
Complexity: Average operations, space .