比起之前那些问计数哈希表的题目,这道题好像更接近哈希表的 底层机制 。
java中hashmap的实现是通过 List<Node> ,即 链表的list ,如果链表过长则换为 红黑树 ,如果容量不足(装填因子下)则 扩充 数组容量。解决冲突的方式是直接 接在对应位置的链表 上。
首先看看哈希表几个操作的时间复杂度:
HashMap的新增:
HashMap的删除,查询都是一样的理解,如果 没得冲突,都是O1的复杂度。
返回 随机元素 ,这个则不好实现,因为HashMap是无序的,又没得类似List那样的索引,很难返回一个random的值。
接着考虑的一个方式就是,能不能把HashMap的key以0,1。。。的方式存到一个数组中,用random得到一个随机的序号,然后在通过序号去找。
然而这里犯了一个错误。这样的方式其实无疑与 把这个HashMap变成了一个LIst 。当然插入是O1,但是删除则不好操作了。
第二个想法是 Hashset ,但问题其实也一样,这是一个无序的set,没办法搞random。这里的无序set指的是 插入进去之后放到的位置就是hash算出来的位置 ,显然无法用随机的方式使得每一个元素返回的概率相同。
第三个想法则是 List作为基础,再用HashMap来补缺陷 。
LIst的操作复杂度:
所以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())); } }