首页 > 代码库 > insert-delete-getrandom-o1-duplicates-allowed
insert-delete-getrandom-o1-duplicates-allowed
https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/public class RandomizedCollection { ArrayList<Integer> nums; HashMap<Integer, Set<Integer>> locs; java.util.Random rand; /** Initialize your data structure here. */ public RandomizedCollection() { rand = new java.util.Random(); nums = new ArrayList<Integer>(); locs = new HashMap<Integer, Set<Integer>>(); } /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */ public boolean insert(int val) { boolean contained = locs.containsKey(val); if (!contained) { locs.put(val, new LinkedHashSet<Integer>()); } locs.get(val).add(nums.size()); nums.add(val); return !contained; } /** Removes a value from the collection. Returns true if the collection contained the specified element. */ public boolean remove(int val) { boolean contained = locs.containsKey(val); if (!contained) { return false; } int index = locs.get(val).iterator().next(); locs.get(val).remove(index); if (index < nums.size()-1) { int change = nums.get(nums.size()-1); nums.set(index, change); locs.get(change).remove(nums.size()-1); locs.get(change).add(index); } nums.remove(nums.size()-1); if (locs.get(val).isEmpty()) { locs.remove(val); } return true; } /** Get a random element from the collection. */ public int getRandom() { return nums.get(rand.nextInt(nums.size())); }}/** * Your RandomizedCollection object will be instantiated and called as such: * RandomizedCollection obj = new RandomizedCollection(); * boolean param_1 = obj.insert(val); * boolean param_2 = obj.remove(val); * int param_3 = obj.getRandom(); */
insert-delete-getrandom-o1-duplicates-allowed
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。