random algorithm

Insert delete getRandom O(1)

we can implement it using following steps:

• create a random number
• come up with some data structure that support O(1) insert and delete operation
• maintain a range of key for the creation of random number

note that, we can not use directly ArrayList, because delete operation would take O(n) time complexity. What we do here is to use map to store the num-index pair. And everytime we need to delete some value, we swap the current value with the last element since all the values are Integer.

class RandomizedSet {

    // store num-index pair
    // key: number
    // value: corresponding index in the arrylist 
    Map<Integer, Integer> map;    
    List<Integer> list;
    /** Initialize your data structure here. */
    public RandomizedSet() {
        map = new HashMap<>();
        list = new ArrayList<>();
    }

    /** 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)) {
            map.put(val, list.size());
            list.add(val);
            return true;
        }
        return false;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (map.containsKey(val)) {
            int index = map.get(val);
            if (index != list.size() - 1) {
                swap(list, map, index, list.size() - 1);
            }
            map.remove(val);
            list.remove(list.size() - 1);
            return true;
        }
        return false;
    }

    /** Get a random element from the set. */
    public int getRandom() {
        int size = list.size();
        int index = (int)(Math.random() * size);

        return list.get(index);
    }

    public void swap(List<Integer> list, Map<Integer, Integer> map, int index, int lastIndex) {
        int temp = list.get(index);
        int tempLast = list.get(lastIndex);

        list.set(index, tempLast);
        list.set(lastIndex, temp);

        map.put(temp, lastIndex);
        map.put(tempLast, index);
    }
}

There are two ways to create a random number,

• Math.random() will return a random number among [0, 1),
  • e.g. (int) (Math.random() * list.size()) return a num from [0, list.size())
• import java.util.random; Random rd = new Random(); rd.nextInt(6) will return a int num from [0, 6)