Leetcode: Insert Delete GetRandom O(1)
2024-10-19 01:27:01
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 1 is the only number in the set, getRandom always return 1.
randomSet.getRandom();
最先想到是用double LinkedList+Map, 没必要,arraylist+map就够了;另外取random的方法还有,rand.nextInt(int n) returns an integer in the range [0, n)
java.util.Random rand = new java.util.Random();
return nums.get( rand.nextInt(nums.size()) );
public class RandomizedSet {
HashMap<Integer, Integer> map;
ArrayList<Integer> arr; /** Initialize your data structure here. */
public RandomizedSet() {
map = new HashMap<Integer, Integer>();
arr = new ArrayList<Integer>();
} /** 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;
arr.add(val);
map.put(val, arr.size()-1);
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 lastItem = arr.get(arr.size()-1);
if (val != lastItem) {
int index = map.get(val);
arr.set(index, lastItem);
map.put(lastItem, index);
}
arr.remove(arr.size()-1);
map.remove(val);
return true;
} /** Get a random element from the set. */
public int getRandom() {
return arr.get((int)(Math.random()*arr.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();
*/
最新文章
- Facebook Paper使用的第三方库
- [Flex] ButtonBar系列——arrowKeysWrapFocus属性如果为 true,则使用箭头键在组件内导航时,如果击中某一端则将折回。
- Codeforces Round #190 (Div. 2) 水果俩水题
- Objective-C MRC多个对象相互引用的内存管理
- ORA-06502: PL/SQL: 数字或值错误 : 字符串缓冲区太小 错误分析
- Ubuntu嵌入式开发环境配置问题集锦(不断更新)
- 基于Servlet、JSP、JDBC、MySQL的一个简单的用户注冊模块(附完整源代码)
- Effective C++之‘宁以pass-by-reference-to-const替换pass-by-value’
- JavaScript原型模式-理解对象
- 20175221 2018-2019-2 《Java程序设计》第二周学习总结
- 位运算练习:将整数A转换为B,需要改变多少个bit位
- App专项测试之弱网测试
- 【UML】NO.53.EBook.6.UML.2.001-【Thinking In UML 大象 第二版】- 概述
- 3. Go语言基本类型
- Sep 15th 2018
- Ocelot——初识基于.Net Core的API网关
- 随手记录一下 Vue 下来框搜索 select2 封装成vue
- POJ-1959 Darts
- 通过ctrl+r快速启动程序
- Item 5:那些被C++默默地声明和调用的函数 Effective C++笔记