面试官最爱问的 O(1) 设计题：支持重复元素的随机集合，到底该怎么实现？

面试官最爱问的 O(1) 设计题：支持重复元素的随机集合，到底该怎么实现？作者：Echo_Wish如果让我评选 LeetCode 设计类题目里最容易"把人绕进去"的一道题，我一定会把这一票投给Randomized Collection（O(1) 时间插入、删除和获取随机元素 II）。很多人第一次看到这道题的时候，第一反应都是：“这不就是 RandomizedSet 的升级版吗？”结果真正开始写代码，没几分钟就发现：事情根本没有想象中那么简单。因为一旦允许元素重复，之前很多看似天衣无缝的数据结构设计，瞬间就失效了。今天，我们就一起把这道经典设计题彻底吃透。不只是知道怎么写，更重要的是理解为什么要这样设计。一、题目到底难在哪里？题目要求设计一个数据结构，需要支持三个操作，并且平均时间复杂度都是O(1)。insert(val) remove(val) getRandom()如果没有"允许重复元素"这一条，其实很多同学都会。经典方案就是：HashMap + ArrayList