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)){
// 已经存在返回false
return false;
}else {
// 长度刚好比索引多一个
this.map.set( val , this.nums.length);
this.nums.push(val);
return true;
}
}
remove(val: number): boolean {
// 如果有的话就删除remove
if(!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]的左边,再和右边相乘得到结果