带权重的随机选择算法

labuladong原创约 2320 字

本文讲解的例题

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

前置知识

阅读本文前，你需要先学习：

写这篇的文章的原因是玩 LOL 手游。我有个朋友抱怨说打排位匹配的队友太菜了，我就说我打排位觉得队友都挺行的啊，好像不怎么坑？

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

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

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

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

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

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

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

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

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

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

528. 按权重随机选择 | 力扣 | LeetCode |

给你一个 下标从 0 开始 的正整数数组 w ，其中 w[i] 代表第 i 个下标的权重。

请你实现一个函数 pickIndex ，它可以 随机地 从范围 [0, w.length - 1] 内（含 0 和 w.length - 1）选出并返回一个下标。选取下标 i 的概率为 w[i] / sum(w) 。

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

示例 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 <= 10⁴
1 <= w[i] <= 10⁵
pickIndex 将被调用不超过 10⁴ 次

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

带权重的随机选择算法

528. 按权重随机选择 https://leetcode.cn/problems/random-pick-with-weight

528. Random Pick with Weight https://leetcode.com/problems/random-pick-with-weight

剑指 Offer II 071. 按权重生成随机数 https://leetcode.cn/problems/cuyjEf

剑指 Offer II 071. 按权重生成随机数 https://leetcode.com/problems/cuyjEf

解法思路

解法代码