LeetCode 哈希表 380. 常数时间插入、删除和获取随机元素(设计数据结构 List HashMap底层 时间复杂…

LeetCode 哈希表 380. 常数时间插入、删除和获取随机元素(设计数据结构 List HashMap底层 时间复杂...

比起之前那些问计数哈希表的题目,这道题好像更接近哈希表的 底层机制

java中hashmap的实现是通过 List<Node> ,即 链表的list ,如果链表过长则换为 红黑树 ,如果容量不足(装填因子下)则 扩充 数组容量。解决冲突的方式是直接 接在对应位置的链表 上。

首先看看哈希表几个操作的时间复杂度:

HashMap的新增:

  1. 计算 key的哈希值
  2. 哈希值作为index,找到对应的 数组位置
  3. 如果数组位置为 ,直接存入
  4. 如果数组位置 不为空遍历该链表,插入末尾

这里考虑理想情况(无冲突),时间复杂度为O1

HashMap的删除,查询都是一样的理解,如果 没得冲突,都是O1的复杂度。

如果冲突,可能出现On情况(链表),Ologn情况(红黑树)

返回 随机元素 ,这个则不好实现,因为HashMap是无序的,又没得类似List那样的索引,很难返回一个random的值。

接着考虑的一个方式就是,能不能把HashMap的key以0,1。。。的方式存到一个数组中,用random得到一个随机的序号,然后在通过序号去找。

然而这里犯了一个错误。这样的方式其实无疑与 把这个HashMap变成了一个LIst 。当然插入是O1,但是删除则不好操作了。

第二个想法是 Hashset ,但问题其实也一样,这是一个无序的set,没办法搞random。这里的无序set指的是 插入进去之后放到的位置就是hash算出来的位置 ,显然无法用随机的方式使得每一个元素返回的概率相同。

第三个想法则是 List作为基础,再用HashMap来补缺陷

LIst的操作复杂度:

  • append,直接在尾端加,O1
  • pop,直接去掉尾端,O1
  • 特定位置插入/删除,都需要萝卜挪坑,On
  • 访问特定位置元素,索引直接访问,O1
  • 查,要跑一遍整个数组,On

所以Random很好做到,其余的需要用 append和pop 搞事

append需要去重,我们把索引和值分别存入HashMap作为辅助

这样要插入时,先用HashMap判断有无(O1),然后直接插尾端(O1)

删除稍麻烦一些,我们如果直接删除真正位置,则需要挪位置变为On

所以用HashMap找到位置后,将该位置和List末尾做交换,然后PoP,这样就是O1了。

class RandomizedSet {
  Map<Integer, Integer> dict;
  List<Integer> list;
  Random rand = new Random();

  /** Initialize your data structure here. */
  public RandomizedSet() {
    dict = new HashMap();
    list = new ArrayList();
  }

  /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
  public boolean insert(int val) {
    if (dict.containsKey(val)) return false;

    dict.put(val, list.size());
    list.add(list.size(), val);
    return true;
  }

  /** Removes a value from the set. Returns true if the set contained the specified element. */
  public boolean remove(int val) {
    if (! dict.containsKey(val)) return false;

    // move the last element to the place idx of the element to delete
    int lastElement = list.get(list.size() - 1);
    int idx = dict.get(val);
    list.set(idx, lastElement);
    dict.put(lastElement, idx);
    // delete the last element
    list.remove(list.size() - 1);
    dict.remove(val);
    return true;
  }

  /** Get a random element from the set. */
  public int getRandom() {
    return list.get(rand.nextInt(list.size()));
  }
}

原文 

http://www.cnblogs.com/take-it-easy/p/13257575.html

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » LeetCode 哈希表 380. 常数时间插入、删除和获取随机元素(设计数据结构 List HashMap底层 时间复杂…

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址