# **Leetcode筆記(Insert Delete GetRandom O(1))**

:::info
:information_source: 題目 : Insert Delete GetRandom O(1), 類型 : hash table , 等級 : medium
日期 : 2023/05/26，2023/06/23，2023/10/03，2023/11/26
:::

### 嘗試
2023/10/03
這一題的難點，要在o(1)之內完成，list在加與刪很方便，但是在刪除時，除非有一個可以直接找到該index的方法，否則要一個一個遍歷，所以這部分可以用dict來做，[數值] = index，index為當下len(list)的長度

class RandomizedSet:

    def __init__(self):
        self.d = dict()
        self.l = list()

    def insert(self, val: int) -> bool:
        if val not in self.d:
            self.d[val] = len(self.l)
            self.l.append(val)
            return True
        return False

    def remove(self, val: int) -> bool:
        if val in self.d:
            # it will change the order by doing normal delete
            # so we have to change it with last

            last_val, index = self.l[-1], self.d[val]
            last_index = len(self.l)
            # change l
            self.l[-1], self.l[index] = val, last_val
            # change d
            self.d[last_val], self.d[val] = index, last_index
            
            # delete l & d
            del self.d[val]
            self.l.pop()

            return True
        return False

    def getRandom(self) -> int:
        return random.choice(self.l)

2023/11/26

class RandomizedSet:

    def __init__(self):
        self.hashmap = {} # key : val / value : index in list
        self.record = [] # index, val
        self.maxIndex = 0

    def insert(self, val: int) -> bool:
        if val in self.hashmap:
            return False
        self.hashmap[val] = self.maxIndex
        self.record.append(val)
        self.maxIndex += 1
        return True

    def remove(self, val: int) -> bool:
        if val not in self.hashmap:
            return False
        index = self.hashmap[val]
        self.record.remove(val)
        del self.hashmap[val]
        return True

    def getRandom(self) -> int:
        return random.choice(self.record)

---
### **優化**

| | hashmap (dict) | array (list) | set |
| ------ | -------------- | ------------ | ---- |
| Insert | O(1) | O(1) | O(1) |
| Delete | O(1) | O(n) | O(1) |

可以用random.choice(list)來取任意數

時間複雜度O(1)，空間複雜度O(n)

class RandomizedSet:

    def __init__(self):
        # 這裡也要有self
        self.d = dict() # [該數字] = 該數字在list中的排序(從0開始)
        self.l = list() # 數字們

    def insert(self, val: int) -> bool:
        if val in self.d:
            return False
        # 需要同時對dict和list操作
        # dict[val] = list目前最新的index
        self.d[val] = len(self.l)
        self.l.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.d:
            return False
        
        lastVal, ind = self.l[-1], self.d[val]
        # 可以不移動val的數字
        # self.l[ind], self.d[lastVal] = lastVal, ind
        
        # 把list中ind位置的數字取代 為最後一個數字
        self.l[ind], self.l[-1] = lastVal, val
        # 把dict中最後一個數字移到ind位置
        self.d[lastVal], self.d[val] = ind, len(self.l)
        self.l.pop()
        del self.d[val]
        return True

    def getRandom(self) -> int:
        return random.choice(self.l)

---

**:warning: 錯誤語法**
:::warning

:::

**:thumbsup:學習**
:::success

:::

**思路**

**講解連結**

Provided by. NeetCode

###### tags: `hash table` `medium` `leetcode`