---
# System prepended metadata

title: '**Leetcode筆記(Random Pick with Weight)**'
tags: [medium, math, microsoft, leetcode]

---

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


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


### 嘗試
```python
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)

![](https://hackmd.io/_uploads/ry5XzZdv2.png)

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


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

```python
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是紀錄後邊界
```
```python
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`