我有個朋友抱怨說打排位匹配的隊友太菜了纫普，我就說我打排位覺得隊友都挺行的啊？我經(jīng)常躺贏昨稼。
朋友意味深長地說了句：一般隱藏分比較高的玩家节视，排位如果排不到實力相當?shù)年犛眩蜁诺揭恍┎斯贰?/p>
嗯假栓？我想了幾秒鐘感覺這小伙子不對勁寻行，他意思是說我隱藏分低，還是說我就是那條菜狗匾荆？
我立馬要求和他開黑打一把拌蜘，證明我不是菜狗，他才是菜狗牙丽。
打完之后我就來發(fā)文了简卧，雖然結(jié)果不便透露，但我對游戲的匹配機制有了一點思考烤芦。
所謂「隱藏分」我不知道是不是真的举娩，畢竟匹配機制是所有競技類游戲的核心環(huán)節(jié)，想必非常復(fù)雜拍棕，不是簡單幾個指標就能搞定的晓铆。
但是如果把這個「隱藏分」機制簡化，倒是一個值得思考的算法問題：系統(tǒng)如何以不同的隨機概率進行匹配绰播？
或者簡單點說骄噪，如何帶權(quán)重地做隨機選擇？
不要覺得這個很容易蠢箩，如果給你一個長度為n的數(shù)組链蕊，讓你從中等概率隨機抽取一個元素，你肯定會做谬泌，random 一個[0, n-1]的數(shù)字出來作為索引就行了滔韵，每個元素被隨機選到的概率都是1/n。
但假設(shè)每個元素都有不同的權(quán)重掌实，權(quán)重地大小代表隨機選到這個元素的概率大小陪蜻，你如何寫算法去隨機獲取元素呢？
力扣第 528 題「按權(quán)重隨機選擇」就是這樣一個問題：
我們就來思考一下這個問題贱鼻，解決按照權(quán)重隨機選擇元素的問題宴卖。
解法思路
這個隨機算法和前綴和技巧和二分搜索技巧能扯上啥關(guān)系？且聽我慢慢道來邻悬。
假設(shè)給你輸入的權(quán)重數(shù)組是w = [1,3,2,1]症昏，我們想讓概率符合權(quán)重，那么可以抽象一下父丰，根據(jù)權(quán)重畫出這么一條彩色的線段：
如果我在線段上面隨機丟一個石子肝谭，石子落在哪個顏色上，我就選擇該顏色對應(yīng)的權(quán)重索引，那么每個索引被選中的概率是不是就是和權(quán)重相關(guān)聯(lián)了攘烛？
所以魏滚，你再仔細看看這條彩色的線段像什么？這不就是前綴和數(shù)組嘛：
那么接下來坟漱，如何模擬在線段上扔石子栏赴？
當然是隨機數(shù)，比如上述前綴和數(shù)組preSum靖秩，取值范圍是[1, 7]，那么我生成一個在這個區(qū)間的隨機數(shù)target = 5竖瘾，就好像在這條線段中隨機扔了一顆石子：
還有個問題沟突，preSum中并沒有 5 這個元素，我們應(yīng)該選擇比 5 大的最小元素捕传，也就是 6惠拭，即preSum數(shù)組的索引 3：
如何快速尋找數(shù)組中大于等于目標值的最小元素？這里就要用到二分搜索了庸论，確切地說是搜索左側(cè)邊界的二分搜索职辅。
到這里，這道題的核心思路就說完了聂示，主要分幾步：
1域携、根據(jù)權(quán)重數(shù)組w生成前綴和數(shù)組preSum。
2鱼喉、生成一個取值在preSum之內(nèi)的隨機數(shù)秀鞭，用二分搜索算法尋找大于等于這個隨機數(shù)的最小元素索引。
3扛禽、最后對這個索引減一（因為前綴和數(shù)組有一位索引偏移）锋边，就可以作為權(quán)重數(shù)組的索引，即最終答案:
解法代碼
上述思路應(yīng)該不難理解编曼，但是寫代碼的時候坑可就多了豆巨。
要知道涉及開閉區(qū)間、索引偏移和二分搜索的題目掐场，需要你對算法的細節(jié)把控非常精確往扔，否則會出各種難以排查的 bug。
下面來摳細節(jié)刻肄，繼續(xù)前面的例子：
就比如這個preSum數(shù)組瓤球，你覺得隨機數(shù)target應(yīng)該在什么范圍取值？閉區(qū)間[0, 7]還是左閉右開[0, 7)敏弃？
都不是卦羡，應(yīng)該在閉區(qū)間[1, 7]中選擇，因為前綴和數(shù)組中 0 本質(zhì)上是個占位符，仔細體會一下：
所以要這樣寫代碼：
int n = preSum.length;// target 取值范圍是閉區(qū)間 [1, preSum[n - 1]]int target = rand.nextInt(preSum[n - 1]) + 1;
接下來绿饵，在preSum中尋找大于等于target的最小元素索引欠肾，應(yīng)該用什么品種的二分搜索？搜索左側(cè)邊界的還是搜索右側(cè)邊界的拟赊？
實際上應(yīng)該使用搜索左側(cè)邊界的二分搜索：
// 搜索左側(cè)邊界的二分搜索
int left_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
return left;
}
前文二分搜索詳解著重講了數(shù)組中存在目標元素重復(fù)的情況刺桃，沒仔細講目標元素不存在的情況。
當目標元素target不存在數(shù)組nums中時吸祟，搜索左側(cè)邊界的二分搜索的返回值可以做以下幾種解讀：
1瑟慈、返回的這個值是nums中大于等于target的最小元素索引。
2屋匕、返回的這個值是target應(yīng)該插入在nums中的索引位置葛碧。
3、返回的這個值是nums中小于target的元素個數(shù)过吻。
比如在有序數(shù)組nums = [2,3,5,7]中搜索target = 4进泼，搜索左邊界的二分算法會返回 2，你帶入上面的說法纤虽，都是對的乳绕。
所以以上三種解讀都是等價的，可以根據(jù)具體題目場景靈活運用逼纸，顯然這里我們需要的是第一種洋措。
綜上，我們可以寫出最終解法代碼：
class Solution {
// 前綴和數(shù)組
private int[] preSum;
private Random rand = new Random();
public Solution(int[] w) {
int n = w.length;
// 構(gòu)建前綴和數(shù)組樊展，偏移一位留給 preSum[0]
preSum = new int[n + 1];
preSum[0] = 0;
// preSum[i] = sum(w[0..i-1])
for (int i = 1; i <= n; i++) {
preSum[i] = preSum[i - 1] + w[i - 1];
}
}
public int pickIndex() {
int n = preSum.length;
// 在閉區(qū)間 [1, preSum[n - 1]] 中隨機選擇一個數(shù)字
int target = rand.nextInt(preSum[n - 1]) + 1;
// 獲取 target 在前綴和數(shù)組 preSum 中的索引
// 搜索左側(cè)邊界的二分搜索
int left = 0, right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (preSum[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
// preSum 的索引偏移了一位呻纹，還原為權(quán)重數(shù)組 w 的索引
return left - 1;
}
}
有了之前的鋪墊，相信你能夠完全理解上述代碼专缠，這道隨機權(quán)重的題目就解決了。
經(jīng)常有讀者留言調(diào)侃涝婉，每次都是看我的文章「云刷題」哥力，看完就會了，也不用親自動手刷了墩弯。
但我想說的是吩跋，很多題目思路一說就懂渔工，但是深入一些的話很多細節(jié)都可能有坑锌钮，本文講的這道題就是一個例子引矩，所以還是建議多實踐梁丘，多總結(jié)。
