380. Insert Delete GetRandom O(1)

二刷 06/2022

用了两个hashmap没有必要，还是应该一个map加一个list

Runtime: 53 ms, faster than 34.57% of Java online submissions for Insert Delete GetRandom O(1).

Memory Usage: 120.2 MB, less than 5.07% of Java online submissions for Insert Delete GetRandom O(1).

class RandomizedSet {

    // key-index, value-node

    Map<Integer, Integer> indexToNum;

    Map<Integer, Integer> numToIndex;

    

    public RandomizedSet() {

        indexToNum = new HashMap<>();

        numToIndex = new HashMap<>();

    }

    

    public boolean insert(int val) {

        if (numToIndex.containsKey(val)) {

            return false;

        }

        int index = indexToNum.size();

        // System.out.printf("index=%d, val=%d\n", index, val);

        indexToNum.put(index, val);

        numToIndex.put(val, index);

        return true;

    }

    

    public boolean remove(int val) {

        if (!numToIndex.containsKey(val)) {

            return false;

        }

        int index = numToIndex.get(val);

        // System.out.printf("num:%d, index:%d\n", val, index);

        int lastIndex = indexToNum.size() - 1;

        // If index is already the last index do nothing

        // Replace the current number with the last number

        if (index != lastIndex) {

            int lastNum = indexToNum.get(lastIndex);

            indexToNum.put(index, lastNum);

            numToIndex.put(lastNum, index);

        }

        indexToNum.remove(lastIndex);

        numToIndex.remove(val);

        return true;

    }

    

    public int getRandom() {

        // Need indexes to generate a random number

        // The number can be accessed by index in O(1) time

        // ArrayList -> remove will take O(N) time

        // LinkedList -> Cannot access by index

        // HashMap<key-index, value-node contains the number> -> remove will swap the last number with the removed number

        // HashMap<key-number, value-index>

        Random rd = new Random();

        int index = rd.nextInt(indexToNum.size());

        // System.out.printf("indexToNum:%s\n", indexToNum.toString());

        // System.out.printf("index=%d", index);

        return indexToNum.get(index);

    }

}

/**

 * 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();

 */

一刷
48.28 %

class RandomizedSet {
    Map<Integer, Integer> map;
    List<Integer> list;
    Random  rd;
    /** Initialize your data structure here. */
    public RandomizedSet() {
        // key-val, value-index of list
        map = new HashMap<>();
        list = new ArrayList<>();
        rd = new Random();
    }
   
    /** 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;
        list.add(val);
        map.put(val, list.size() - 1);
        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 pos = map.get(val);
        if (pos != list.size() - 1) {
            swapDelete(val);
        } else {
            deleteLast(val);
        }
        return true;
    }
   
    private void swapDelete(int val) {
        int tail = list.get(list.size() - 1);
        int pos = map.get(val);
        // before swap: val -> pos, tail -> list.size() - 1
        // after swap: val -> list.size() - 1, tail -> pos
        list.set(pos, tail);
        map.put(tail, pos);
        deleteLast(val);
    }
    private void deleteLast(int val) {
        list.remove(list.size() - 1);
        map.remove(val);
    }
   
    /** Get a random element from the set. */
    public int getRandom() {
        int pos = rd.nextInt(list.size());
        return list.get(pos);
    }
}