Java | Leetcode Java题解之第381题O(1)时间插入、删除和获取随机元素-允许重复

本文主要是介绍Java | Leetcode Java题解之第381题O(1)时间插入、删除和获取随机元素-允许重复，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

题解：

class RandomizedCollection {Map<Integer, Set<Integer>> idx;List<Integer> nums;/** Initialize your data structure here. */public RandomizedCollection() {idx = new HashMap<Integer, Set<Integer>>();nums = new ArrayList<Integer>();}/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */public boolean insert(int val) {nums.add(val);Set<Integer> set = idx.getOrDefault(val, new HashSet<Integer>());set.add(nums.size() - 1);idx.put(val, set);return set.size() == 1;}/** Removes a value from the collection. Returns true if the collection contained the specified element. */public boolean remove(int val) {if (!idx.containsKey(val)) {return false;}Iterator<Integer> it = idx.get(val).iterator();  int i = it.next();int lastNum = nums.get(nums.size() - 1);nums.set(i, lastNum);idx.get(val).remove(i);idx.get(lastNum).remove(nums.size() - 1);if (i < nums.size() - 1) {idx.get(lastNum).add(i);}if (idx.get(val).size() == 0) {idx.remove(val);}nums.remove(nums.size() - 1);return true;}/** Get a random element from the collection. */public int getRandom() {return nums.get((int) (Math.random() * nums.size()));}
}

这篇关于Java | Leetcode Java题解之第381题O(1)时间插入、删除和获取随机元素-允许重复的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---