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(n2)
優化：也是左邊成右邊的，但是我們先左邊乘積：從左到右遍歷，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]的左邊,再和右邊相乘得到結果
