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.
HashMap<Integer, Integer> map; List<Integer> nums; Random random; /** Initialize your data structure here. */ publicRandomizedSet(){ map = new HashMap<>(); nums = new ArrayList<>(); random = new Random(); } /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */ publicbooleaninsert(int val){ if (!map.containsKey(val)){ nums.add(val); map.put(val,nums.size()-1); returntrue; } else { returnfalse; } } /** Removes a value from the set. Returns true if the set contained the specified element. */ publicbooleanremove(int val){ if (!map.containsKey(val)) returnfalse; else { int index = map.get(val); if (index < nums.size()-1){ nums.set(index, nums.get(nums.size()-1)); map.put(nums.get(nums.size()-1), index); } nums.remove(nums.size()-1); map.remove(val); returntrue; } } /** Get a random element from the set. */ publicintgetRandom(){ 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(); */