LeetCode_随机化_中等_380. O(1) 时间插入、删除和获取随机元素

- 日理万妓 2023-10-06 22:23 37阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

实现 **RandomizedSet** 类：

RandomizedSet() 		//初始化 RandomizedSet 对象
    bool insert(int val) 	//当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
    bool remove(int val) 	//当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
    int getRandom() 		//随机返回现有集合中的一项(测试用例保证调用此方法时集合中至少存在一个元素)。每个元素应该有相同的概率被返回。

你必须实现类的所有函数，并满足**每个函数的平均时间复杂度为 O(1)** 。

**示例：**

输入
    ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
    [[], [1], [2], [2], [], [1], [2], []]
    输出
    [null, true, false, true, 2, true, false, 2]
    解释
    RandomizedSet randomizedSet = new RandomizedSet();
    randomizedSet.insert(1); 	// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
    randomizedSet.remove(2); 	// 返回 false ，表示集合中不存在 2 。
    randomizedSet.insert(2); 	// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
    randomizedSet.getRandom(); 	// getRandom 应随机返回 1 或 2 。
    randomizedSet.remove(1); 	// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
    randomizedSet.insert(2); 	// 2 已在集合中，所以返回 false 。
    randomizedSet.getRandom(); 	// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。

**提示：**  
\-231 <= val <= 231 \- 1  
最多调用 insert、remove 和 getRandom 函数 2 \* 105 次  
在调用 getRandom 方法时，数据结构中至少存在一个元素。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/insert-delete-getrandom-o1

## 2.思路 ##

（1）随机化  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————随机化
    class RandomizedSet {
        
    
        // nums 用于存储元素
        List<Integer> nums;
        // indices 记录 nums 中的每个元素(键)以及其在 nums 中对应的索引(值)
        HashMap<Integer, Integer> indices;
        //定义随机数对象
        Random random;
    
        public RandomizedSet() {
        
            //初始化
            nums = new ArrayList<>();
            indices = new HashMap<>();
            random = new Random();
        }
        
        public boolean insert(int val) {
        
            if (indices.containsKey(val)) {
        
                // indices 中已存在 val，故返回 false
                return false;
            } else {
        
                //记录 nums 的长度，即接下将要插入的元素 val 的索引
                int index = nums.size();
                //向 nums 中插入 val
                nums.add(val);
                //在 indices 中记录 val 在 nums 中的索引
                indices.put(val, index);
                return true;
            }
        }
        
        public boolean remove(int val) {
        
            if (!indices.containsKey(val)) {
        
                // indices 中不存在 val，故返回 false
                return false;
            } else {
        
                //获取要移除的元素 val 在 nums 中的索引
                int valIndex = indices.get(val);
                //获取 nums 中最后一个元素
                int last = nums.get(nums.size() - 1);
                // set(index, val): 替换 nums 中指定索引的元素
                nums.set(valIndex, last);
                //更新 indices 中元素 last 的索引
                indices.put(last, valIndex);
                //移除元素val
                nums.remove(nums.size() - 1);
                //删除 indices 中 val 及其索引的记录
                indices.remove(val);
                return true;
            }
        }
        
        public int getRandom() {
        
            // random.nextInt(nums.size()): 生成一个 [0, nums.size() - 1] 之间任意整数
            int randomIndex = random.nextInt(nums.size());
            return nums.get(randomIndex);
        }
    }
    
    /**
     * 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();
     */

[Link 1]: https://leetcode-cn.com/problems/insert-delete-getrandom-o1/solution/o1-shi-jian-cha-ru-shan-chu-he-huo-qu-su-rlz2/