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)。