首页 > 代码库 > insert-delete-getrandom-o1-duplicates-allowed

insert-delete-getrandom-o1-duplicates-allowed

https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/public class RandomizedCollection {    ArrayList<Integer> nums;    HashMap<Integer, Set<Integer>> locs;    java.util.Random rand;    /** Initialize your data structure here. */    public RandomizedCollection() {        rand = new java.util.Random();        nums = new ArrayList<Integer>();        locs = new HashMap<Integer, Set<Integer>>();    }        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */    public boolean insert(int val) {        boolean contained = locs.containsKey(val);        if (!contained) {            locs.put(val, new LinkedHashSet<Integer>());        }        locs.get(val).add(nums.size());        nums.add(val);        return !contained;    }        /** Removes a value from the collection. Returns true if the collection contained the specified element. */    public boolean remove(int val) {        boolean contained = locs.containsKey(val);        if (!contained) {            return false;        }        int index = locs.get(val).iterator().next();        locs.get(val).remove(index);        if (index < nums.size()-1) {            int change = nums.get(nums.size()-1);            nums.set(index, change);            locs.get(change).remove(nums.size()-1);            locs.get(change).add(index);        }        nums.remove(nums.size()-1);        if (locs.get(val).isEmpty()) {            locs.remove(val);        }        return true;            }        /** Get a random element from the collection. */    public int getRandom() {        return nums.get(rand.nextInt(nums.size()));    }}/** * Your RandomizedCollection object will be instantiated and called as such: * RandomizedCollection obj = new RandomizedCollection(); * boolean param_1 = obj.insert(val); * boolean param_2 = obj.remove(val); * int param_3 = obj.getRandom(); */

 

insert-delete-getrandom-o1-duplicates-allowed