528. 按權重隨機選擇

給定一個正整數數組 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 次

解題思路

維護一個前綴和數組，里面的前綴和元素，就是每個區間的邊界，因此我們隨機生成一個[1,sum]之間的數字，再根據這個數字在前綴和數組中用二分查找搜索其位于的區間

代碼

class Solution {int[] pre;int sum;public Solution(int[] w) {int n=w.length;pre=new int[n];pre[0]=w[0];for(int i=1;i<n;i++)pre[i]=pre[i-1]+w[i];sum=pre[n-1];}public int pickIndex() {int idx=(int)(Math.random()*sum)+1;return bs(idx);}public int bs(int tar) {int l=0,r=pre.length-1;while(l<r){int mid=(r-l)/2+l;if(pre[mid]<tar){l=mid+1;}else {r=mid;}}return l;}
}/*** Your Solution object will be instantiated and called as such:* Solution obj = new Solution(w);* int param_1 = obj.pickIndex();*/