[LeetCode]Insert Delete GetRandom O(1)

插入删除O(1)，我们会想到hashmap + linkedlist，但是要求O(1)的get random显然这无法达到，所以我们要考虑其他的数据结构。显然hashmap还是需要的，那么为了实现O(1)的get random我们可以尝试用array。那么array的缺点是容量是固定的，满了之后我们要把array里的所有元素copy到一个更大的array当中，那么我们还能达到O(1)的时间复杂度么？
我们分析平摊时间(armortized time)，假设array初始容量为1，每次满了之后double size，那么插入n个元素的总的时间复杂度是O(n)。因为我们总共会double log2(n)次array，也就是说总的double的时间复杂度为1 + 2 + 4 + ... + 2^(log2(n)) = O(n)。也就是说平摊到每一次操作上，时间复杂度就是O(1)。所以用dynamic array是可行的，我们不需要自己去implement，因为c++，java都有自带的vector和arraylist。
我们可以保证insert和get random的常数时间，那么delete应该怎么做呢。显然我们不能简单的=地delete然后将后面的所有数向前平移一格。这里我们每次将要删除的数和最后的数交换，更新hashmap，然后删除最后的数即可。代码如下：