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