381. Insert Delete GetRandom O(1) - Duplicates allowed

 一刷 06/2022

Version #1 ArrayList + HashMap

写了一个bug就是不能只检查hashmap.containsKey, 而应该检查里面的set是不是空

因为remove的时候并没有把空set移除掉

Runtime: 44 ms, faster than 74.74% of Java online submissions for Insert Delete GetRandom O(1) - Duplicates allowed.

Memory Usage: 94.9 MB, less than 72.59% of Java online submissions for Insert Delete GetRandom O(1) - Duplicates allowed.

class RandomizedCollection {

    Map<Integer, Set<Integer>> indexes;

    List<Integer> nums;

    public RandomizedCollection() {

        indexes = new HashMap<>();

        nums = new ArrayList<>();

    }

    

    public boolean insert(int val) {

        boolean presents = indexes.containsKey(val) && indexes.get(val).size() > 0;

        indexes.putIfAbsent(val, new HashSet<>());

        int index = nums.size();

        nums.add(val);

        indexes.get(val).add(index);

        return !presents;

    }

    

    public boolean remove(int val) {

        if (!indexes.containsKey(val) || indexes.get(val).size() == 0) {

            return false;

        }

        int lastIndex = nums.size() - 1;

        Set<Integer> numIndexes = indexes.get(val);

        if (!numIndexes.contains(lastIndex)) {

            // swap one of the element with the last number

            int index = numIndexes.iterator().next();

            indexes.get(val).remove(index);

            int lastNum = nums.get(lastIndex);

            indexes.get(lastNum).remove(lastIndex);

            indexes.get(lastNum).add(index);

            nums.set(index, lastNum);

        } else {

            numIndexes.remove(lastIndex);

        }

        nums.remove(lastIndex);

        return true;

    }

    

    public int getRandom() {

        Random rd = new Random();

        return nums.get(rd.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();

 */