Problem: 380. O(1) 时间插入、删除和获取随机元素
文章目录
- 思路
- 复杂度
- Code
思路
👩🏫 三叶题解
复杂度
时间复杂度: O ( 1 ) O(1) O(1)
空间复杂度: O ( n ) O(n) O(n)
Code
class RandomizedSet {
static int[] nums = new int[200_010];//存元素的值
Random random = new Random();
Map<Integer, Integer> map = new HashMap<>();//key:元素的值,val:元素在nums数组中的下标
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 cur = map.remove(val);//删除当前元素在 map 中的键值对,并返回 值(待删除元素在数组中的下标)
if(cur != idx)//如果最后一个元素就是要删除的元素,直接跳过
map.put(nums[idx],cur);//更新最后一个元素在数组中的下标
nums[cur] = nums[idx--];//最后一个元素与当前元素交换,然后删除最后一个元素
return true;
}
public int getRandom() {
return nums[random.nextInt(idx+1)];
}
}
/**
* 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();
*/