题目大意：
常数时间插入、删除和获取随机元素
设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。
- insert(val)：当元素 val 不存在时，向集合中插入该项。
- remove(val)：元素 val 存在时，从集合中移除该项。
- getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。
示例 :
// 初始化一个空的集合。 RandomizedSet randomSet = new RandomizedSet(); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。 randomSet.insert(1); // 返回 false ，表示集合中不存在 2 。 randomSet.remove(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。 randomSet.insert(2); // getRandom 应随机返回 1 或 2 。 randomSet.getRandom(); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。 randomSet.remove(1); // 2 已在集合中，所以返回 false 。 randomSet.insert(2); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。 randomSet.getRandom();
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=380
解题思路分析：
本题实质上是考察如何使用存储对象。java中List类和Set类都可以存储，而且都有contains方法判断集合内是否含有某个元素，List类由于没有索引， contains 方法的时间复杂度为n，而Set类的时间复杂度是1，因此在查看是否包含某个元素时，使用Set类更为高效，同时也符合题目O(1)的要求。另外，使用List还有一个问题，在删除元素时，我们事先不知道该元素所在的位置，因此 O(1) 的时间复杂度下肯定不能解决问题。
然而Set类也有一个缺陷，我们无法从中随机取出一个元素，然而List则可以实现，只要我们随机产生一个index下标，从List中取出该元素即可。
因此，综上所述，我们应该采用一个折中的方法，即利用List和HashMap来实现。 HashMap与Set实际上原理相同，惟一的区别在于， HashMap 除了key，还能存一个Value，可以理解为Set的加强版。
insert方法中，我们首先查看HashMap中是否存在当前数字， HashMap的搜索时间复杂度为O(1),符合题目要求。如果不存在的话，我们将当前数字添加到List中，同时，将当前数作为key，以及他在list中的index作为value存入到HashMap中。
remove方法中，我们可以通过HashMap快速得到被删除数字在list中的index，此时利用index从List中删除元素的时间复杂度是 O(1)，符合题目要求，但是，我们不能这样做！！原因是，如果我们利用index删除了List中的该元素之后，位于该元素后面的元素所在的index都会相应减一，这与存储在map中的数值就无法保证一致。此时的做法应该是，我们将List中要删除的index的值更新为List的尾元素，同时更新Map中该尾元素所在的位置为index。这两个操作的时间复杂度均为O(1)。最后再将List中最后一个元素删除，同时将被删除元素在map中删除即可。
getRandom方法很简单，利用List的元素个数作为取值范围，随机生成一个数字作为下标，返回List中改下标元素即可。
实现代码：
List<Integer> list = new ArrayList<>();
Map<Integer,Integer> map = new HashMap<>();
Random random = new Random();
/** Initialize your data structure here. */
public RandomizedSet() {
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
boolean contain = map.containsKey(val);
if(!contain){
map.put(val,list.size());
list.add(val);
}
return !contain;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
boolean contain = map.containsKey(val);
if(contain){
int lastIndex=list.size()-1;
int removeIndex=map.get(val);
int lastNum=list.get(lastIndex);
list.set(removeIndex, lastNum);
list.remove(lastIndex);
map.put(lastNum, removeIndex);
map.remove(val);
}
return contain;
}
/** Get a random element from the set. */
public int getRandom() {
int randomValue = random.nextInt(list.size());
return list.get(randomValue);
}本题解法执行时间为14ms。
Runtime: 14 ms, faster than 32.28% of Java online submissions for Insert Delete GetRandom O(1).
Memory Usage: 53.8 MB, less than 14.00% of Java online submissions for Insert Delete GetRandom O(1).
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-380-insert-delete-getrandom-o1-解题思路分析/