2 HashSet + 1 ArrayList Java solution, 139 ms, beats 70%


  • 0
    L
    public class RandomizedCollection {
        private int cnt;
        private HashMap<Integer, HashSet<Integer>> map; // Key: val Value: set of index
        private HashMap<Integer, HashSet<Integer>> ref; // Key: index Value: set of index
        private ArrayList<Integer> nums;
        private Random ran;
        /** Initialize your data structure here. */
        public RandomizedCollection() {
            cnt = 0;
            map = new HashMap<>();
            ref = new HashMap<>();
            nums = new ArrayList<>();
            ran = new Random();
        }
        
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        public boolean insert(int val) {
            if (!map.containsKey(val))
                map.put(val, new HashSet<>());
            HashSet<Integer> set = map.get(val);
            if (cnt >= nums.size())
                nums.add(val);
            nums.set(cnt, val);
            ref.put(cnt, set);
            set.add(cnt);
            cnt++;
            return set.size() == 1;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        public boolean remove(int val) {
            if (!map.containsKey(val))
                map.put(val, new HashSet<>());
            HashSet<Integer> set = map.get(val);
            if (set.isEmpty())
                return false;
            Integer idx = set.iterator().next();
            set.remove(idx);
            --cnt;
            if (idx != cnt) {
                nums.set(idx, nums.get(cnt));
                set = ref.get(cnt);
                set.remove(cnt);
                set.add(idx);
                ref.put(idx, set);
            }
            return true;
        }
        
        /** Get a random element from the collection. */
        public int getRandom() {
            return nums.get(ran.nextInt(cnt));
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.