Info

数据结构精品课 和 递归算法专题课 限时附赠网站会员，全新纸质书《labuladong 的算法笔记》 出版，签名版限时半价！

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
528. Random Pick with Weight	528. 按权重随机选择	🟠
-	剑指 Offer II 071. 按权重生成随机数	🟠

写这篇的文章的原因是玩 LOL 手游。

我有个朋友抱怨说打排位匹配的队友太菜了，我就说我打排位觉得队友都挺行的啊，好像不怎么坑？

朋友意味深长地说了句：一般隐藏分比较高的玩家，排位如果排不到实力相当的队友，就会排到一些菜狗。

嗯？我想了几秒钟感觉这小伙子不对劲，他意思是说我隐藏分低，还是说我就是那条菜狗？

我立马要求和他开黑打一把，证明我不是菜狗，他才是菜狗。开黑结果这里不便透露，大家猜猜吧。

打完之后我就来发文了，因为我对游戏的匹配机制有了一点思考。

所谓「隐藏分」我不知道是不是真的，毕竟匹配机制是所有竞技类游戏的核心环节，想必非常复杂，不是简单几个指标就能搞定的。

但是如果把这个「隐藏分」机制简化，倒是一个值得思考的算法问题：系统如何以不同的随机概率进行匹配？

或者简单点说，如何带权重地做随机选择？

不要觉得这个很容易，如果给你一个长度为 n 的数组，让你从中等概率随机抽取一个元素，你肯定会做，random 一个 [0, n-1] 的数字出来作为索引就行了，每个元素被随机选到的概率都是 1/n。

但假设每个元素都有不同的权重，权重地大小代表随机选到这个元素的概率大小，你如何写算法去随机获取元素呢？

力扣第 528 题「按权重随机选择」就是这样一个问题：

我们就来思考一下这个问题，解决按照权重随机选择元素的问题。

本文剩余内容为会员内容，请先购买 网站会员 ，然后 借助 Chrome 插件解锁网页 或者 点这里 跳转小鹅通查看。