数组|380. O(1) 时间插入、删除和获取随机元素

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

题目： 实现RandomizedSet 类：
RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数，并满足每个函数的平均时间复杂度为 O(1) 。
题目链接： 380. O(1) 时间插入、删除和获取随机元素
解题思路及相关代码：
一个数组存储元素
一个哈希表存储<元素值，数组对应下标> 这样可以在O(1)复杂度完成随机取数操作
删除时将数组末尾元素移到被删除元素的位置，同时更新哈希表
如果要删除的元素是末尾元素则不执行移动操作

class RandomizedSet {public Map<Integer,Integer> map;public int[] numsArray;Random random;public int ids=0;public RandomizedSet() {map=new HashMap<>();numsArray=new int[20001];random = new Random();}public boolean insert(int val) {//检查该数字是否存在if(!map.containsKey(val)){numsArray[ids]=val;map.put(val,ids);ids++;return true;}else{return false;}}public boolean remove(int val) {if(map.containsKey(val)){int index=map.get(val);numsArray[index]=numsArray[ids-1];int loc=map.remove(val);//当最后一个节点需要被删除时 不需要重新插入if(loc!=ids-1)map.put(numsArray[index],index);ids--;return true;}else{return false;}}public int getRandom() {int randomIndex = random.nextInt(ids);return numsArray[randomIndex];}
}