本题有点类似设计题
    原本想到了大体思路：

    • HashMap<Integer, Integer>: key是存的val，value是ArrayList<Integer>的index
    • ArrayList<Integer>: 存的是val

    但是一开始没有想明白如果remove元素的话，那么HashMap<Integer, Integer>里存的index就都变了，在被删除的元素的后面的index都会自动往前移动1
    看了答案后想明白了，可以在删除前，手动把要删除的元素移动到ArrayList<Integer>的末尾，这样就可以避免这个问题。

    • 时间复杂度：
      • insert(): 380. Insert Delete GetRandom O(1) - 图1
      • remove(): 380. Insert Delete GetRandom O(1) - 图2
      • getRandom(): 380. Insert Delete GetRandom O(1) - 图3
    • 空间复杂度：380. Insert Delete GetRandom O(1) - 图4

    代码如下：

    1. class RandomizedSet {
    3.   private Map<Integer, Integer> mySet;
    4.   private List<Integer> myList;
    5.   private Random rand;
    7.   /** Initialize your data structure here. */
    8.   public RandomizedSet() {
    9.     mySet = new HashMap<>();
    10.     myList = new ArrayList<>();
    11.     rand = new Random();
    12.   }
    14.   /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    15.   public boolean insert(int val) {
    16.     if (mySet.containsKey(val)) {
    17.       return false;
    18.     }
    19.     myList.add(val);
    20.     mySet.put(val, myList.size() - 1);
    21.     return true;
    22.   }
    24.   /** Removes a value from the set. Returns true if the set contained the specified element. */
    25.   public boolean remove(int val) {
    26.     if (!mySet.containsKey(val)) {
    27.       return false;
    28.     }
    29.     int oldIdx = mySet.get(val);
    30.     if (oldIdx != myList.size() - 1) {
    31.       int swapVal = myList.get(myList.size() - 1);
    32.       mySet.put(swapVal, oldIdx);
    33.       myList.set(oldIdx, swapVal);
    34.     }
    35.     mySet.remove(val);
    36.     myList.remove(myList.size() - 1);
    37.     return true;
    38.   }
    40.   /** Get a random element from the set. */
    41.   public int getRandom() {
    42.     return myList.get(rand.nextInt(myList.size()));
    43.   }
    44. }
    46. /**
    47.  * Your RandomizedSet object will be instantiated and called as such:
    48.  * RandomizedSet obj = new RandomizedSet();
    49.  * boolean param_1 = obj.insert(val);
    50.  * boolean param_2 = obj.remove(val);
    51.  * int param_3 = obj.getRandom();
    52.  */