Linkedin 电面

hashMap<流水号, value> random delete 要swap pop or push 就是新增流水号 这样因该是amortized o(1)? 能接受吗?

风不清 发表于 2018-1-16 03:23
请问一下hashMap + Doubly linkedList这个具体是什么做key, 什么做value 呀？

请看daguanyuan的回复，hashmap key是node reference， val是index

这个题好难啊！面的时候碰到肯定死了。。。不理解random delete怎么实现。。。

风不清 发表于 2018-1-16 08:12
谢谢楼主回复！我就是看了他写的然后有点confusing. 是不是 stack是用 doubly linkedlist 实现，然后再多 ...

需要三个数据结构，stack本身doubly linked list，然后需要利用利口380的方法，一个arraylist一个hashmap。

jerrytjz 发表于 2018-1-16 10:05
需要三个数据结构，stack本身doubly linked list，然后需要利用利口380的方法，一个arraylist一个hashmap ...

我觉得只需要一个hashmap和一个双链表就行了吧?
直接在存{node: idx}的hashmap里面random出来一个node, 然后去double linkedlist里面删除这个node, 就可以了吧

BeStrong2017 发表于 2018-6-27 14:25
我觉得只需要一个hashmap和一个双链表就行了吧?
直接在存{node: idx}的hashmap里面random出来一个node,  ...

怎么保证用O（1）的复杂度 在hashmap里找到一个random node？

谢谢大大分享!!

分享一下我的想法，看看对不对，借鉴了LC380 的想法， 三种操作都是 O(1) 的时间复杂度
会需要用到 double linked list，array 和 hashmap

push：

• 创建一个新的 node， 添加到 list 的队尾
• 将此 node 加入 array
• 将此 node 和在 array 中的 index 加入 hashmap (node作为 key，index作为 value)
  

pop：

• 把 list 的最后一个 node 从 list 中去除
• 从 hashmap 得到此 node 在 array 中的 index，然后将此 node 从 hashmap 中删除
• 将此 node 与 array 最后一个元素 (记为 node_a) 互换位置， 同时更新 hashmap 中 node_a 的 index，然后将 array 的队尾去除
  

randomRemove：

• 用 random 函数得到一个在array长度范围内的随机整数，作为 index，得到在 array 中此 index 上的 node
• 用 pop 第2，3步类似的方法将此 node 从 array 和 hashmap 中删除
• 将此 node 从 list 中删除