转载

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
正文到此结束
Loading...