leetcode 380. Insert Delete GetRandom O(1) | 380. O(1) 时间插入、删除和获取随机元素（Java）

左手的ㄟ右手 2022-08-31 06:56 71阅读 0赞

## 题目 ##

[https://leetcode.com/problems/insert-delete-getrandom-o1/][https_leetcode.com_problems_insert-delete-getrandom-o1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

一个设计题，没想出来，参考了：[  
Java solution using a HashMap and an ArrayList along with a follow-up. (131 ms)][Java solution using a HashMap and an ArrayList along with a follow-up. _131 ms]

class RandomizedSet { 
        java.util.Random rand = new java.util.Random();
    
        List<Integer> list;
        Map<Integer,Integer> map;
    
        /** Initialize your data structure here. */
        public RandomizedSet() { 
            list = new ArrayList<>();
            map = new HashMap<>();
        }
    
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        public boolean insert(int val) { 
            if (map.containsKey(val)) { 
                return false;
            } else { 
                map.put(val, list.size());
                list.add(val);
                return true;
            }
        }
    
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        public boolean remove(int val) { 
            if (!map.containsKey(val)) return false;
            int i = map.get(val);
            if (i != list.size() - 1) { 
                int last = list.get(list.size() - 1);
                list.set(i, last);
                map.put(last, i);
            }
            list.remove(list.size() - 1);
            map.remove(val);
            return true;
        }
    
        /** Get a random element from the set. */
        public int getRandom() { 
            return list.get(rand.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(); */

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_insert-delete-getrandom-o1]: https://leetcode.com/problems/insert-delete-getrandom-o1/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/9e8561c96bba4f0580201c002f53bd47.png
[Java solution using a HashMap and an ArrayList along with a follow-up. _131 ms]: https://leetcode.com/problems/insert-delete-getrandom-o1/discuss/85401/Java-solution-using-a-HashMap-and-an-ArrayList-along-with-a-follow-up.-%28131-ms%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/6a3791cccec343ecaf52f55b7e7e82df.png