为了保证常数时间插入和获取采用可变数组存储数据，那么在删除一个随机元素时如果需要移动元素需要n时间复杂度，那么进一步优化可以采用哈希表获取删除元素所在的位置然后把最后一个元素覆盖到要删除的位置最后再把最后一个元素删除掉，这样就可以避免循环移动覆盖的时间开销
class RandomizedSet {private List<Integer> nums;private Map<Integer,Integer> indicies;private Random random;public RandomizedSet() {nums = new ArrayList<>();indicies = new HashMap<>();random = new Random();}public boolean insert(int val) {if (indicies.containsKey(val)) {return false;} else {int index = nums.size();nums.add(val);indicies.put(val, index);return true;}}public boolean remove(int val) {if (!indicies.containsKey(val)) {return false;} else {//将最后一个元素覆盖到要删除的元素，再删除最后一个元素Integer index = indicies.get(val);Integer lastValue = nums.get(nums.size() - 1);nums.set(index, lastValue);nums.remove(nums.size() - 1);indicies.put(lastValue, index);indicies.remove(val);return true;}}public int getRandom() {return nums.get(random.nextInt(nums.size()));}
}/*** Your RandomizedSet object will be instantiated and called as such:* RandomizedSet obj = new RandomizedSet();* boolean param_1 = obj.insert(val);* boolean param_2 = obj.remove(val);* int param_3 = obj.getRandom();*/