P192. 支持随机获取元素的集合(允许重复)

leetcode 381 lintcode 954 设计 哈希表 数组 讨论

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

描述

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

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