Design a data structure that supports all following operations in average O(1) time.
insert(val): Inserts an item val to the set if not already present. remove(val): Removes an item val from the set if present. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
classRandomizedSet{ HashMap<Integer, Integer> indexMap; ArrayList<Integer> set; /** Initialize your data structure here. */ publicRandomizedSet(){ indexMap = new HashMap<>(); set = new ArrayList<>(); } /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */ publicbooleaninsert(int val){ if(indexMap.containsKey(val)) returnfalse; indexMap.put(val, set.size()); set.add(val); returntrue; } /** Removes a value from the set. Returns true if the set contained the specified element. */ publicbooleanremove(int val){ if(!indexMap.containsKey(val)) returnfalse; int index = indexMap.get(val); // 在ArrayList中,交换最后一个index if(index != set.size() - 1){ int lastNum = set.get(set.size() - 1); set.set(index, lastNum); indexMap.put(lastNum, index); } indexMap.remove(val); set.remove(set.size() - 1); returntrue; } /** Get a random element from the set. */ publicintgetRandom(){ Random random = new Random(); int index = random.nextInt(set.size()); return set.get(index); } }