7.3 380. O(1) 时间插入、删除和获取随机元素
实现RandomizedSet 类：
RandomizedSet()初始化RandomizedSet对象bool insert(int val)当元素val不存在时，向集合中插入该项，并返回true；否则，返回false。bool remove(int val)当元素val存在时，从集合中移除该项，并返回true；否则，返回false。int getRandom()随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。
之前没有写过类，现在写起来确实有点不太顺手，多练练就好啦！
我们要维护两个对象：
- 随机访问（getRandom()）：数组支持 O(1) 时间复杂度的随机访问（通过索引直接获取元素），而哈希表（
Map）虽然可以快速查找元素是否存在，但无法直接随机访问元素。 - 存储元素顺序：数组可以按插入顺序存储元素，而哈希表是无序的，无法直接支持随机访问。
插入逻辑：判断是否存在(map高效判断)+数组push+map.set
删除逻辑：将最后一个数覆盖要删除的数，然后删除最后一个数(数组pop)，map(delete)
我的代码：
class RandomizedSet {// 第一次写集合还挺不习惯的// 不能在构造函数里面创造，要考虑作用域的问题private map: Map<number, number>; // 值到索引的映射private nums: number[]; // 存储所有值的数组constructor() {// 进行初始化this.map = new Map();this.nums = [];}insert(val: number): boolean {// 如果有数字就要插入到map末尾if(this.map.has(val)){// 已经存在返回falsereturn false;}else {// 长度刚好比索引多一个this.map.set( val , this.nums.length);this.nums.push(val);return true;}}remove(val: number): boolean {// 如果有的话就删除removeif(!this.map.has(val)){return false;}// 有值就要删除// 因为数组只有删除前面或者删除后面,我们想要达到O(1)就不能够遍历// 我们把要删除的数一道最后一个位置,直接pop// 得到index:const index = this.map.get(val);// 获取最后一个数let lastValue = this.nums[this.nums.length - 1];// 进行替换,同时要替换map的最后一个书的索引this.nums[index] = lastValue;this.map.set(lastValue , index);// 删除最后一个数字this.nums.pop();this.map.delete(val);return true;}getRandom(): number {const randomIndex = Math.floor(Math.random() * this.nums.length);return this.nums[randomIndex];}
}/*** Your RandomizedSet object will be instantiated and called as such:* var obj = new RandomizedSet()* var param_1 = obj.insert(val)* var param_2 = obj.remove(val)* var param_3 = obj.getRandom()*/// O(1):哈希表
// 数组的一些方法：includes，pop总结：
RandomizedSet 类通过结合哈希表和数组来实现。哈希表用于快速查找元素是否存在及其在数组中的索引，数组用于支持随机访问和高效地添加、删除元素。插入时，元素被添加到数组末尾，并在哈希表中记录其索引；删除时，通过交换待删除元素与数组末尾元素的方式，确保删除操作的时间复杂度为 O(1)；获取随机元素时，通过生成随机索引直接从数组中获取。这种组合使得所有操作都能在平均 O(1) 时间内完成。
7.3 238. 除自身以外数组的乘积
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 **不要使用除法，**且在 O(n) 时间复杂度内完成此题。
我最开始的思路：
当前的数的左边的数乘右边的数
我的代码：
function productExceptSelf(nums: number[]): number[] {// 当前的数let cur = 0;// 左边的指针let left = 0 ;// 右边的指针let right = 0 ; // 对每一个都要进行遍历// 最后的答案let ans = [] ;let subLeft = 1 ;let subRight = 1 ; for(cur ; cur < nums.length ; cur++){left=0;right = nums.length - 1;subLeft = 1 ;subRight = 1;// `左边while(left < cur){subLeft = subLeft * nums[left];left++;}// 右边while(right > cur){subRight = subRight * nums[right];right--;}ans.push(subLeft * subRight);}return ans;
}
时间超限:双重循环（外层 for 循环 + 内层两个 while 循环），导致时间复杂度为 O(n²)
优化：也是左边成右边的，但是我们先左边乘积：从左到右遍历，ans[i] 初始化为左边所有元素的乘积。然后右边乘积：从右到左遍历，将 ans[i] 乘以右边所有元素的乘积。
优化后的代码：
function productExceptSelf(nums: number[]): number[] {// 对每一个都要进行遍历// 最后的答案let ans = [] ;let subLeft = 1 ;let subRight = 1 ; for(let i = 0 ;i < nums.length ; i++){ans[i] = subLeft;subLeft *= nums[i];}for(let i = nums.length - 1 ; i >= 0 ; i--){ans[i] *= subRight;subRight *= nums[i];}return ans;
}总结：计算每一个nums[i]的左边,再和右边相乘得到结果
