Design a data structure that supports all following operations in averageO(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.

用hashmap HE array list

public class RandomizedSet {
    //since this does not allow duplicate 
    List<Integer> nums;
    Map<Integer, Integer> map;
    Random rand;
    public RandomizedSet() {
        // do intialization if necessary
        map = new HashMap<>();
        nums = new ArrayList<>();
        rand = new Random();
    }

    /*
     * @param val: a value to the set
     * @return: true if the set did not already contain the specified element or false
     */
    public boolean insert(int val) {
        // write your code here
        if (map.containsKey(val)) {
            return false;
        }
        map.put(val, nums.size()); // number and index;
        nums.add(val);
        return true;
    }

    /*
     * @param val: a value from the set
     * @return: true if the set contained the specified element or false
     */
    public boolean remove(int val) {
        // write your code here
        if (!map.containsKey(val)) {
            return false;
        }
        int loc = map.get(val);
        // o (1) time 
       if (loc < nums.size() - 1 ) { // not the last one than swap the last one with this val
            int lastone = nums.get(nums.size() - 1 );
            nums.set( loc , lastone );
            map.put(lastone, loc);
        }
        map.remove(val);
        nums.remove(nums.size() - 1);
        return true;
    }

    /*
     * @return: Get a random element from the set
     */
    public int getRandom() {
        // write your code here
        int range = nums.size() ;

        return nums.get(rand.nextInt(range));
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param = obj.insert(val);
 * boolean param = obj.remove(val);
 * int param = obj.getRandom();
 */