面试官最爱问的 O(1) 神题：插入、删除、随机获取竟然都能做到常数时间？看完彻底搞懂！

面试官最爱问的 O(1) 神题：插入、删除、随机获取竟然都能做到常数时间？看完彻底搞懂！作者：Echo_Wish如果让我评选一道最能考察数据结构设计能力的面试题，那我一定会把Insert Delete GetRandom O(1)放进去。很多人第一次看到这道题的时候，第一反应都是：插入 O(1)？没问题。删除 O(1)？哈希表也能做到。获取随机元素？随机拿一个不就好了？可真正开始写代码的时候，很快就发现问题来了。哈希表虽然能 O(1) 找到元素，但是没办法 O(1) 随机获取某个元素。数组虽然能够 O(1) 根据下标随机访问，但是删除元素又不是 O(1)。于是你会发现，这道题真正考察的不是某一种数据结构，而是：如何把两种数据结构组合起来，让它们互相弥补短板。很多优秀算法题都是这样。真正难的不是算法，而是设计。今天，我们就一起把这道经典题彻底拆开。一、题目到底要求什么？题目要求实现一个数据结构，它需要支持三个操作：in