温馨提示:您没有权限查看当前视频。 立即购买观看视频
这个题目说的是,你要设计一个增加版的集合(Collection),它要支持以下操作:插入元素(insert)、删除元素(remove)以及随机获取元素(getRandom)。
注意,这 3 个操作的平均时间复杂度都要求是 O(1)。另外,这个集合中允许存储重复元素,一个元素被随机返回的概率与它在集合中的数量正相关。
以下是这个集合的使用示例: // 初始化一个空集合 RandomizedCollection c = new RandomizedCollection(); // 成功插入数字 3,返回 true。c: [3] c.insert(3); // 3 已经在集合中,返回 false。c: [3, 3] c.insert(3); // 成功插入数字 6,返回 true。c: [3, 3, 6] c.insert(6); // 2/3 的概率返回 3,1/3 的概率返回 6。 // c: [3, 3, 6] c.getRandom(); // 成功删除数字 3,返回 true。c: [3, 6] c.remove(3); // 8 不在集合中,返回 false。c: [3, 6] c.remove(8); // 以 1/2 的概率返回 3 或 6。c: [3, 6] c.getRandom();
AlgoCasts 旨在用心做好每一个算法讲解视频。每个视频包含两个部分:题目的剖析讲解以及编码,力求在讲解清楚到位的基础上,尽可能地保持视频精简短小,让大家可以在碎片时间里进行学习,并收获这些算法题背后的思想与乐趣。