class RandomizedSet {
    // list：变长数组，用于存储集合中的元素，保证 getRandom() 能够在 O(1) 时间内随机访问
    List<Integer> list = new ArrayList<>();
    // map：哈希表，用于存储元素值 val 到其在 list 中对应下标 index 的映射，保证查找和删除是 O(1)
    Map<Integer, Integer> map = new HashMap<>();
    // rand：随机数生成器，用于在 getRandom() 时生成随机的数组下标
    Random rand = new Random();

    public RandomizedSet() {
    }
    
    public boolean insert(int val) {
        // 如果 map 中已经存在该元素，说明插入失败，直接返回 false
        if (map.containsKey(val)) {
            return false;
        }
        // 如果不存在，获取当前 list 的长度（即新元素应该存放的索引）
        int size = list.size();
        // 将新元素追加到数组的末尾
        list.add(val);
        // 在哈希表中记录元素和它的索引位置
        map.put(val, size);
        return true;
    }
    
    public boolean remove(int val) {
        if (map.containsKey(val)) {
            // 核心技巧：不能直接对 list 按索引 remove，否则后面的元素会向前平移，导致时间复杂度变为 O(N)
            
            // 获取数组末尾的那个元素值
            int last = list.get(list.size() - 1);
            // 获取当前要删除的元素 val 在数组中的索引
            int index = map.get(val);

            // 1. 在哈希表中，将末尾元素 last 的索引更新为当前要删除元素的索引 index
            map.put(last, index);
            // 2. 在数组中，将末尾元素 last 直接覆盖到当前要删除元素的索引位置
            list.set(index, last);
            
            // 3. 删除数组的最后一个元素（原本的 val 已经被覆盖，现在移走的是 原本 last 的冗余副本）
            list.remove(list.size() - 1);
            // 4. 从哈希表中移除元素 val 的记录
            map.remove(val);
            return true;
        } else {
            // 如果 map 中不存在该元素，说明删除失败，返回 false
            return false;
        }
    }
    
    public int getRandom() {
        // rand.nextInt(list.size()) 生成一个 [0, list.size()) 范围内的随机下标
        // 然后直接从数组中取出该下标的元素返回
        return list.get(rand.nextInt(list.size()));
    }
}