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