insert/get/Random【避免漂移问题】

我一开始的做法： 我也意思到必须用ArrayList  + HashMap 但是问题是arrylist的size 会shrink，一shrink position就乱了。

正解：主要是Remove那个地方我不会写。

OMG....

这个Trick在于每次要删的时候把要删的值和 array最后一个数交换一个位置并且update一下HashMap里的position。这样的话，remove的时候就不会发现position的漂移了

比如说：

如果你把position 3的位置删了，整个array的size都会shrink。然后本来4的位置的东西就会到3，5的位置东西会到4.。。

然后我们本来HashMap里的索引也就没用了。

解决办法就是每次把remove val pos和最后一个数的pos交换，这样虽然数组缩小，但是pos没有位移！

• 人面猴

  序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...

  沈念sama阅读 200,612评论 5赞 471
• 死咒

  序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...

  沈念sama阅读 84,345评论 2赞 377
• 救了他两次的神仙让他今天三更去死

  文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...

  开封第一讲书人阅读 147,625评论 0赞 332
• 道士缉凶录：失踪的卖姜人

  文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...

  开封第一讲书人阅读 54,022评论 1赞 272
• 港岛之恋（遗憾婚礼）

  正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...

  茶点故事阅读 62,974评论 5赞 360
• 恶毒庶女顶嫁案：这布局不是一般人想出来的

  文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...

  开封第一讲书人阅读 48,227评论 1赞 277
• 城市分裂传说

  那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...

  沈念sama阅读 37,688评论 3赞 392
• 双鸳鸯连环套：你想象不到人心有多黑

  文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...

  开封第一讲书人阅读 36,358评论 0赞 255
• 万荣杀人案实录

  序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...

  沈念sama阅读 40,490评论 1赞 294
• 护林员之死

  正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...

  茶点故事阅读 35,402评论 2赞 317
• 白月光启示录

  正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...

  茶点故事阅读 37,446评论 1赞 329
• 活死人

  序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...

  沈念sama阅读 33,126评论 3赞 315
• 日本核电站爆炸内幕

  正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...

  茶点故事阅读 38,721评论 3赞 303
• 男人毒药：我在死后第九天来索命

  文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...

  开封第一讲书人阅读 29,802评论 0赞 19
• 一桩弑父案，背后竟有这般阴谋

  文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...

  开封第一讲书人阅读 31,013评论 1赞 255
• 情欲美人皮

  我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...

  沈念sama阅读 42,504评论 2赞 346
• 代替公主和亲

  正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...

  茶点故事阅读 42,080评论 2赞 341

推荐阅读更多精彩内容

• LeetCode/LintCode ReviewPage 题解-总结

  背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪：刷leetcod...

  土汪阅读 12,716评论 0赞 33
• GeekBand-笔记-05

  总结：侯老师的这门stl课，只看视频和ppt是不太够的。应该结合侯老师的《stl源码剖析》和Nicolai M J...

  诵之思之阅读 233评论 3赞 0
• 想写作没灵感？给我一个笔记本！

  近几年，“手账”在国内迅速流行起来，不仅相关的书籍和周边产品销量火爆，各位手账达人的自媒体平台也吸引了众多粉丝。 ...

  火残翼阅读 661评论 0赞 11
• 2017年4月12日

  跟黄灵去健身房之前，去吃了个蒸饺和炒粉。到了健身房，我不是特别想上瑜伽课，但想想还是进去了。效果特别不好，一点...

  大胖胖企鹅阅读 174评论 0赞 0
• 非暴力沟通及其作用

  ——魏君学习非暴力沟通心得 我常听到人们说非暴力沟通是什么以及有何作用。据我的经验都是根据自己对非暴力沟通的了解，...

  魏君NVC阅读 6,331评论 2赞 1