LEETCODE 380. Insert Delete GetRandom O(1) 解题思路分析

题目大意:

常数时间插入、删除和获取随机元素

设计一个支持在平均 时间复杂度 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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。