GetRandom O(1)

380. Insert Delete GetRandom O(1)

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.

• List 儲存 val

• Map 儲存 val, store index

• Remove val in list in constant, so we swap the number with last number in list and then delete the number in last position, it's O(1) operation

class RandomizedSet {
    List<Integer> list;
    Map<Integer, Integer> map;

    /** Initialize your data structure here. */
    public RandomizedSet() {
        list = new ArrayList<>();
        map = new HashMap<>();
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if(map.containsKey(val)) return false;
        map.put(val, list.size());
        System.out.println(val);
        list.add(val);
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if(!map.containsKey(val)) return false;
        int idx = map.get(val);

        // swap the val and last val in list
        if(idx < list.size()-1){
            int lastNum = list.get(list.size()-1);
            list.set(idx, lastNum);
            map.put(lastNum, idx);
        }
        list.remove(list.size()-1);
        map.remove(val);

        return true;
    }

    /** Get a random element from the set. */
    public int getRandom() {
        Random ran = new Random();
        return list.get(ran.nextInt(list.size()));
    }
}

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

Same as 380, but with duplicated number

• List store numbers

• Map> indexes to the same numbers

class RandomizedCollection {
    List<Integer> list;
    Map<Integer, Set<Integer>> map;
    /** Initialize your data structure here. */
    public RandomizedCollection() {
        list = new ArrayList<>();
        map = new HashMap<>();
    }

    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        boolean contain = map.containsKey(val);
        if(!contain) map.put(val, new HashSet<>());
        map.get(val).add(list.size());
        list.add(val);
        return !contain;
    }

    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        if(!map.containsKey(val)) return false;
        int idx = map.get(val).iterator().next();
        map.get(val).remove(idx);
        if(map.get(val).size() == 0) map.remove(val); 

        if(idx < list.size()-1){
            int lastNum = list.get(list.size()-1);
            list.set(idx, lastNum);
            map.get(lastNum).remove(list.size()-1);
            map.get(lastNum).add(idx);
        }
        list.remove(list.size()-1);

        return true;
    }

    /** Get a random element from the collection. */
    public int getRandom() {
        Random ran = new Random();
        return list.get(ran.nextInt(list.size()));
    }
}