AI summary
type
status
date
slug
summary
category
tags
icon
password

带权重的随机选择

所谓「隐藏分」我不知道是不是真的，毕竟匹配机制是所有竞技类游戏的核心环节，想必非常复杂，不是简单几个指标就能搞定的。
但是如果把这个「隐藏分」机制简化，倒是一个值得思考的算法问题：系统如何以不同的随机概率进行匹配？
或者简单点说，如何带权重地做随机选择？
不要觉得这个很容易，如果给你一个长度为 n 的数组，让你从中等概率随机抽取一个元素，你肯定会做，random 一个 [0, n-1] 的数字出来作为索引就行了，每个元素被随机选到的概率都是 1/n。
但假设每个元素都有不同的权重，权重地大小代表随机选到这个元素的概率大小，你如何写算法去随机获取元素呢？

528. 按权重随机选择

给你一个 下标从 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%）。
前文 小而美的算法技巧：前缀和数组 加上 二分搜索算法核心代码模版 能够解决带权重的随机选择算法。
这个随机算法和前缀和技巧和二分搜索技巧能扯上啥关系？且听我慢慢道来。
假设给你输入的权重数组是 w = [1,3,2,1]，我们想让概率符合权重，那么可以抽象一下，根据权重画出一条彩色的线段。
如果我在线段上面随机丢一个石子，石子落在哪个颜色上，我就选择该颜色对应的权重索引，那么每个索引被选中的概率是不是就是和权重相关联了？
所以，你再仔细看看这条彩色的线段像什么？这不就是 [前缀和数组] 嘛：
notion image
那么接下来，如何模拟在线段上扔石子？
当然是随机数，比如上述前缀和数组 preSum，取值范围是 [1, 7]，那么我生成一个在这个区间的随机数 target = 5，就好像在这条线段中随机扔了一颗石子：
还有个问题，preSum 中并没有 5 这个元素，我们应该选择比 5 大的最小元素，也就是 6，即 preSum 数组的索引 3：
notion image
如何快速寻找数组中大于等于目标值的最小元素？[二分搜索算法] 就是我们想要的。
到这里，这道题的核心思路就说完了，主要分几步：
  1. 根据权重数组 w 生成前缀和数组 preSum。
  1. 生成一个取值在 preSum 之内的随机数，用二分搜索算法寻找大于等于这个随机数的最小元素索引。
  1. 最后对这个索引减一（因为前缀和数组有一位索引偏移），就可以作为权重数组的索引，即最终答案
上述思路应该不难理解，但是写代码的时候坑可就多了。
下面来抠细节，继续前面的例子：
就比如这个 preSum 数组，你觉得随机数 target 应该在什么范围取值？闭区间 [0, 7] 还是左闭右开 [0, 7)？
都不是，应该在闭区间 [1, 7] 中选择，理解成一个个离散的点，不要理解成线段：
  • target=1 对应 preSum[1]
  • target=2,3,4 对应 preSum[2]
  • target=5,6 对应 preSum[3]
  • target=7 对应 preSum[4]
这样不就正好与题目中要求的概率对应上了。
别忘了前缀和数组和原始数组有一位索引偏移，所以 left_bound 得到的索引应该减一。
接下来，在 preSum 中寻找大于等于 target 的最小元素索引，应该用什么品种的二分搜索？搜索左侧边界的还是搜索右侧边界的？
还记得搜索左侧边界的二分搜索的几种解读吗：
  1. 返回的这个值是 nums 中大于等于 target 的最小元素索引。
  1. 返回的这个值是 target 应该插入在 nums 中的索引位置。
  1. 返回的这个值是 nums 中小于 target 的元素个数。
显然这里我们需要的是第一种。
完整代码如下：

田忌赛马

田忌赛马的故事大家应该都听说过：
田忌和齐王赛马，两人的马分上中下三等，如果同等级的马对应着比赛，田忌赢不了齐王。但是田忌遇到了孙膑，孙膑就教他用自己的下等马对齐王的上等马，再用自己的上等马对齐王的中等马，最后用自己的中等马对齐王的下等马，结果三局两胜，田忌赢了。
当然，这段历史也挺有意思的，那个讽齐王纳谏，自恋的不行的邹忌和田忌是同一时期的人，他俩后来就杠上了。不过这是题外话，我们这里就打住。
以前学到田忌赛马课文的时，我就在想，如果不是三匹马比赛，而是一百匹马比赛，孙膑还能不能合理地安排比赛的顺序，赢得齐王呢？
当时没想出什么好的点子，只觉得这里面最核心问题是要尽可能让自己占便宜，让对方吃亏。总结来说就是，打得过就打，打不过就拿自己的垃圾和对方的精锐互换。
不过，我一直没具体把这个思路实现出来，直到最近刷到力扣第 870 题「优势洗牌」，一眼就发现这是田忌赛马问题的加强版：

870. 优势洗牌

给定两个长度相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。
返回 nums1 的 任意 排列，使其相对于 nums2 的优势最大化。
这就像田忌赛马的情景，nums1 就是田忌的马，nums2 就是齐王的马，数组中的元素就是马的战斗力，你就是孙膑，展示你真正的技术吧。
仔细想想，这个题的解法还是有点扑朔迷离的。什么时候应该放弃抵抗去送人头，什么时候应该硬刚？这里面应该有一种算法策略来最大化「优势」。
送人头一定是迫不得已而为之的权宜之计，否则隔壁田忌就会以为你是齐王买来的演员。只有田忌的上等马比不过齐王的上等马时，才会用下等马去和齐王的上等马互换。
对于比较复杂的问题，可以尝试从特殊情况考虑。
你想，谁应该去应对齐王最快的马？肯定是田忌最快的那匹马，我们简称一号选手。
如果田忌的一号选手比不过齐王的一号选手，那其他马肯定是白给了，显然这种情况应该用田忌垫底的马去送人头，降低己方损失，保存实力，增加接下来比赛的胜率。
但如果田忌的一号选手能比得过齐王的一号选手，那就和齐王硬刚好了，反正这把田忌可以赢。
你也许说，这种情况下说不定田忌的二号选手也能干得过齐王的一号选手？如果可以的话，让二号选手去对决齐王的一号选手，不是更节约？
就好比，如果考 60 分就能过的话，何必考 90 分？每多考一分就亏一分，刚刚好卡在 60 分是最划算的。
这种节约的策略是没问题的，但是没有必要。这也是本题有趣的地方，需要绕个脑筋急转弯：
我们暂且把田忌的一号选手称为 T1，二号选手称为 T2，齐王的一号选手称为 Q1。
如果 T2 能赢 Q1，你试图保存己方实力，让 T2 去战 Q1，把 T1 留着是为了对付谁？
显然，你担心齐王还有战力大于 T2 的马，可以让 T1 去对付。
但是你仔细想想，现在 T2 已经是可以战胜 Q1 的，Q1 可是齐王的最快的马耶，齐王剩下的那些马里，怎么可能还有比 T2 更强的马？
所以，没必要节约，最后我们得出的策略就是：
将齐王和田忌的马按照战斗力排序，然后按照排名一一对比。如果田忌的马能赢，那就比赛，如果赢不了，那就换个垫底的来送人头，保存实力。
根据这个思路，我们需要对两个数组排序，但是 nums2 中元素的顺序不能改变，因为计算结果的顺序依赖 nums2 的顺序，所以不能直接对 nums2 进行排序，而是利用其他数据结构来辅助。
同时，最终的解法还用到前文 双指针技巧秒杀七道数组题目 总结的双指针算法模板，用以处理「送人头」的情况：
算法的时间复杂度很好分析，也就是二叉堆和排序的复杂度 。