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

题目

https://leetcode.com/problems/insert-delete-getrandom-o1/

题解

一个设计题，没想出来，参考了：
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();*/

总结

以上是生活随笔为你收集整理的leetcode 380. Insert Delete GetRandom O(1) | 380. O(1) 时间插入、删除和获取随机元素（Java）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。