我一开始的做法: 我也意思到必须用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没有位移!