文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給定一個正整數數組 w ，其中 w[i] 代表下標 i 的權重（下標從 0 開始），請寫一個函數 pickIndex ，它可以隨機地獲取下標 i，選取下標 i 的概率與 w[i] 成正比。

例如，對于 w = [1, 3]，挑選下標 0 的概率為 1 / (1 + 3) = 0.25 （即，25%），
而選取下標 1 的概率為 3 / (1 + 3) = 0.75（即，75%）。

也就是說，選取下標 i 的概率為 w[i] / sum(w) 。

示例 1： 輸入： ["Solution","pickIndex"] [[[1]],[]] 輸出： [null,0] 解釋： Solution solution = new Solution([1]); solution.pickIndex(); // 返回 0，因為數組中只有一個元素，所以唯一的選擇是返回下標 0。示例 2： 輸入： ["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"] [[[1,3]],[],[],[],[],[]] 輸出： [null,1,1,1,1,0] 解釋： Solution solution = new Solution([1, 3]); solution.pickIndex(); // 返回 1，返回下標 1，返回該下標概率為 3/4 。 solution.pickIndex(); // 返回 1 solution.pickIndex(); // 返回 1 solution.pickIndex(); // 返回 1 solution.pickIndex(); // 返回 0，返回下標 0，返回該下標概率為 1/4 。由于這是一個隨機問題，允許多個答案， 因此下列輸出都可以被認為是正確的: [null,1,1,1,1,0] [null,1,1,1,1,1] [null,1,1,1,0,0] [null,1,1,1,0,1] [null,1,0,1,0,0] ...... 諸若此類。提示： 1 <= w.length <= 10000 1 <= w[i] <= 10^5 pickIndex 將被調用不超過 10000 次

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/random-pick-with-weight
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

類似題目：
LeetCode 497. 非重疊矩形中的隨機點（前綴和+二分查找）

• 計算前綴和權重
• 隨機權值，二分查找，找到權值落在的區間點

class Solution {vector<int> w_presum;int total; public:Solution(vector<int>& w) {w_presum = w;for(int i = 1; i < w.size(); ++i)w_presum[i] += w_presum[i-1];total = w_presum.back();}int pickIndex() {int w = rand()%total + 1;int L = 0, R = w_presum.size()-1, mid;while(L <= R){mid = L+((R-L)>>1);if(w_presum[mid] < w)L = mid+1;else{if(mid==0 || w_presum[mid-1] < w)return mid;elseR = mid-1;}}return -1;} };

88 ms 39.3 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的LeetCode 528. 按权重随机选择（前缀和+二分查找）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。