LeetCode Top Interview Questions 380. Insert Delete GetRandom O(1) (Java版; Meidum)

拼搏现实的明天。 2023-07-03 02:33 89阅读 0赞

### [welcome to my blog][] ###

## LeetCode Top Interview Questions 380. Insert Delete GetRandom O(1) (Java版; Meidum) ##

#### 题目描述 ####

Design a data structure that supports all following operations in average O(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.
    Example:
    
    // Init an empty set.
    RandomizedSet randomSet = new RandomizedSet();
    
    // Inserts 1 to the set. Returns true as 1 was inserted successfully.
    randomSet.insert(1);
    
    // Returns false as 2 does not exist in the set.
    randomSet.remove(2);
    
    // Inserts 2 to the set, returns true. Set now contains [1,2].
    randomSet.insert(2);
    
    // getRandom should return either 1 or 2 randomly.
    randomSet.getRandom();
    
    // Removes 1 from the set, returns true. Set now contains [2].
    randomSet.remove(1);
    
    // 2 was already in the set, so return false.
    randomSet.insert(2);
    
    // Since 2 is the only number in the set, getRandom always return 2.
    randomSet.getRandom();

#### 第一次做; new Random().nextInt(6)随机输出\[0,6)之间的整数; 覆盖操作的技巧可以降低ArrayList删除元素的开销, 毕竟ArrayList删除最后一个元素不需要大规模调整数组; 待删除的元素, 如果该元素不是最后一个元素则需要执行覆盖操作, 让最后一个元素覆盖当前元素, 然后删掉最后一个元素 ####

class RandomizedSet { 
        private List<Integer> list;
        private Map<Integer, Integer> map;
        Random random;
        /** Initialize your data structure here. */
        public RandomizedSet() { 
            list = new ArrayList<>();
            map = new HashMap<>();
            random = new Random();
            
        }
        
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        public boolean insert(int val) { 
            boolean flag = map.containsKey(val);
            //不考虑重复元素
            if(flag)
                return false;
            //此时list.size()是val的索引
            map.put(val, list.size());
            //加入list
            list.add(val);
            return !flag;
            
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        public boolean remove(int val) { 
            //先判断val是否存在
            //ArrayList的contains和HashMap的containsKey有什么区别? 平均时间复杂度一样吗? arraylist和hashmap的remove平均时间复杂度一样吗?
            boolean flag = map.containsKey(val);
            if(!flag)
                return false;
            //
            int index = map.get(val);
            //如果val不是list中的最后一个元素就不用执行覆盖操作了, 直接删除即可
            if(index<list.size()-1){ 
                //让list中的最后一个元素覆盖index位置的元素, 然后删除list最后一个元素, 这样就不用大规模调整数组了
                int tmp = list.get(list.size()-1);
                list.set(index, tmp);
                //覆盖之后,调整该元素在map中的索引
                map.put(tmp, index);
            }
            //从list中删除
            list.remove(list.size()-1);
            //从map中删除
            //hashmap的remove操作是O(1)吗?
            map.remove(val);
            return true;
        }
        
        /** Get a random element from the set. */
        public int getRandom() { 
            return list.get(random.nextInt(list.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(); */

#### [力扣官方题解分析][Link 1] ####

![format_png][]

[welcome to my blog]: https://littlehaes.com
[Link 1]: https://leetcode-cn.com/problems/insert-delete-getrandom-o1/solution/chang-shu-shi-jian-cha-ru-shan-chu-he-huo-qu-sui-j/
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS8yOGE0OGE3NTE3ODJhOTRiMTQzYjUxNGI2MmQ4MjMzNC94bWxub3RlL0IwQTVBRjFFQUY3OTRBOUU5QjUwRUI5MEIyMTI4MkVCLzU2Nzc5?x-oss-process=image/format,png