# **Leetcode筆記(Random Pick with Weight)**

:::info
:information_source: 題目 : Random Pick with Weight, 類型 : math , 等級 : medium
日期 : 2023/06/15
:::

### 嘗試

class Solution:

    def __init__(self, w: List[int]):
        self.total = 0
        self.l = []
        for n in w:
            self.total += n
            self.l.append(self.total)

    def pickIndex(self) -> int:
        target = random.randint(1, self.total)
        res = 0
        for i in range(len(self.l)):
            if target <= self.l[i]:
                return i

---
### **優化**
重新複習了binary search模板

舉例 : 數列[1, 2, 3]，出現的機率為[1/6, 2/6, 3/6]，也可以用整數區間替換，(0,1], (1,2,3], (3,4,5,6]，也就是[1], [2,3], [4,5,6]，也就是[1], [3], [6]
之後在讓python隨機取1~6的數字，選到某個數字後，用binary search下去找那個數字的位置(index)


random.randint(a, b) 是 Python 中 random 模組中的一個函式，它會返回一個在 [a, b] 範圍內（包括 a 和 b）隨機生成的整數

這段程式碼的時間複雜度為 O(log n)，其中 n 是列表 `w` 的長度。這是因為該程式碼使用了二分搜索算法
空間複雜度為 O(n)，其中 n 是列表 `w` 的長度。這是因為在初始化時，該程式碼創建了一個 `post` 列表來存儲前綴和。

class Solution:

    def __init__(self, w: List[int]):
        self.post = []
        accu = 0
        for n in w:
            accu += n
            self.post.append(accu)

    def pickIndex(self) -> int:
        total = self.post[-1]
        target = random.randint(1, total)

        l, r = 0, len(self.post) - 1
        while l <= r:
            mid = (l + r) // 2
            if target < self.post[mid]:
                r = mid - 1
            elif target > self.post[mid]:
                l = mid + 1
            else:
                return mid
        return l # 因為post是紀錄後邊界

class Solution:

    def __init__(self, w: List[int]):
        self.total = 0
        self.l = []
        for n in w:
            self.total += n
            self.l.append(self.total)
        self.w = w

    def pickIndex(self) -> int:
        target = random.randint(1, self.total)
        l, r = 0, len(self.w) - 1
        while l <= r:
            mid = (l + r) // 2
            if target > self.l[mid]:
                l = mid + 1
            elif target < self.l[mid]:
                r = mid - 1
            else:
                return mid

        return l

---

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

:::

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

:::

**思路**

**講解連結**
https://www.youtube.com/watch?v=_z7UfMpYTXI
Provided by. Timothy H Chang

###### tags: `math` `medium` `leetcode`