P188. 支持随机获取元素的集合

leetcode 380 lintcode 657 设计 哈希表 数组 讨论

温馨提示:您没有权限查看当前视频。 立即购买观看视频

描述

这个题目说的是,你要设计一个增加版的集合(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

AlgoCasts 旨在用心做好每一个算法讲解视频。每个视频包含两个部分:题目的剖析讲解以及编码,力求在讲解清楚到位的基础上,尽可能地保持视频精简短小,让大家可以在碎片时间里进行学习,并收获这些算法题背后的思想与乐趣。