380. Insert Delete GetRandom O(1)

time: all O(1)

space: O(1~n)

class RandomizedSet {

    private List<Integer> nums;
    private Map<Integer, Integer> numToIndex; // map<num, num's index>
    private Random rand;
    
    public RandomizedSet() {
        nums = new ArrayList<>();
        numToIndex = new HashMap<>();
        rand = new Random();
    }
    
    public boolean insert(int val) {
        //if insert ok return true, or false
        if (numToIndex.containsKey(val)) {
            return false;
        }
        numToIndex.put(val, nums.size()); // 
        nums.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        //if remove ok return true, or false
        if (!numToIndex.containsKey(val)) {
            return false;
        }
        // how to not shift each index? 
        // if not delete last num, replace delete num's position by last num, then delete last num
        // deleteNum,xxxxx  lastNum
        int deleteNumIndex = numToIndex.get(val);
        int lastNum = nums.get(nums.size()-1);
        if (deleteNumIndex != nums.size()-1) {
            nums.set(deleteNumIndex, lastNum);
            numToIndex.put(lastNum,deleteNumIndex);
        }
        nums.remove(nums.size()-1);
        numToIndex.remove(val);
        return true;
    }
    
    public int getRandom() {
        // guaranteed that at least one element exists when this method is called
        return nums.get(rand.nextInt(nums.size()));
    }
}

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