Java O(1) 时间插入、删除和获取随机元素

实现RandomizedSet 类：

        RandomizedSet() 初始化 RandomizedSet 对象
        bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
        bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
        int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
        你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

class RandomizedSet {

    static int[] nums;
    Random rand;
    HashMap map;
    int index = -1;
    
    public RandomizedSet() {
        this.nums = new int[200001];
        this.rand = new Random();
        this.map = new HashMap<>();
    }
    
    public boolean insert(int val) {
        if( map.containsKey(val) ){
            return false;
        }
        map.put(val,++index);
        nums[index] = val;
        return true;
    }
    
    public boolean remove(int val) {
        if( !map.containsKey(val) ){
            return false;
        }
        int local = map.remove(val);

        //如果元素位置不是最后一个，交换位置
        if(local != index){
            map.put(nums[index],local);
        }
        nums[local] = nums[index--];
        return true;
    }
    
    public int getRandom() {
        return nums[rand.nextInt(index+1)];
    }
}

执行用时：22 ms, 在所有 Java 提交中击败了61.97%的用户

内存消耗：85.9 MB, 在所有 Java 提交中击败了81.16%的用户

通过测试用例：19 / 19