题目链接
题目描述
实现代码
个人实现代码:
class RandomizedSet {
Map<Integer, Boolean> containMap = new HashMap();
int size = 0;
Random rand = new Random();
public RandomizedSet() {
}
public boolean insert(int val) {
if(getVal(val)) {
return false;
}
containMap.put(val, true);
size++;
return true;
}
public boolean remove(int val) {
if(getVal(val)) {
containMap.remove(val);
size--;
return true;
}
return false;
}
public int getRandom() {
int index = rand.nextInt(size) + 1;
int val = 0;
for(Map.Entry<Integer, Boolean> entry : containMap.entrySet()) {
val = entry.getKey();
if(--index == 0) {
break;
}
}
return val;
}
private Boolean getVal(int key) {
return containMap.get(key) != null;
}
}
/**
* 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();
*/
参考大佬实现思想:
- 定义一个map,一个数组nums,和一个整型变量size
- map的key为元素的值,value为该元素在nums数组中的存放索引;
- 当insert时,通过map判断是否存在,不存在则map、nums中都插入,同时size+1;
- 当remove时,通过map判断是否存在,存在则通过map的value找到在数组nums中的位置,将其与size位置即最后一个位置的元素进行交换,size-1;
实现代码:
class RandomizedSet {
static int[] nums = new int[200010];
Random random = new Random();
Map<Integer, Integer> map = new HashMap<>();
int idx = -1;
public boolean insert(int val) {
if (map.containsKey(val)) return false;
nums[++idx] = val;
map.put(val, idx);
return true;
}
public boolean remove(int val) {
if (!map.containsKey(val)) return false;
int loc = map.remove(val);
if (loc != idx) map.put(nums[idx], loc);
nums[loc] = nums[idx--];
return true;
}
public int getRandom() {
return nums[random.nextInt(idx + 1)];
}
}
PS:个人参考思想以后写的代码没AC,离谱:
class RandomizedSet {
Map<Integer, Integer> map = new HashMap();
int[] nums = new int[100002];
int size = 0;
Random rand = new Random();
public RandomizedSet() {
}
public boolean insert(int val) {
if(map.containsKey(val)) {
return false;
}
map.put(val, size);
nums[size++] = val;
return true;
}
public boolean remove(int val) {
Integer location = map.get(val);
if(location == null) {
return false;
}
map.remove(val);
nums[location] = nums[--size];
map.put(nums[location], location);
return true;
}
public int getRandom() {
return nums[rand.nextInt(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();
*/