随机数在实际的工作中拥有很广泛的用途。比如说，产生随机数进行验证等等。

接下来以一个力扣的题来举例：

528. 按权重随机选择

给定一个正整数数组 w ，其中 w[i] 代表位置 i 的权重，请写一个函数 pickIndex ，它可以随机地获取位置 i，选取位置 i 的概率与 w[i] 成正比。

说明:

1 <= w.length <= 10000

1 <= w[i] <= 10^5

pickIndex 将被调用不超过 10000 次

示例1:

输入:

[“Solution”,”pickIndex”]

[[[1]],[]]

输出: [null,0]

示例2:

输入:

[“Solution”,”pickIndex”,”pickIndex”,”pickIndex”,”pickIndex”,”pickIndex”]

[[[1,3]],[],[],[],[],[]]

输出: [null,0,1,1,1,0]

输入语法说明：

输入是两个列表：调用成员函数名和调用的参数。Solution 的构造函数有一个参数，即数组 w。pickIndex 没有参数。输入参数是一个列表，即使参数为空，也会输入一个 [] 空列表。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/random-pick-with-weight

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

  1. class Solution {
  2. public:
  3.     vector<int>prob;
  4.     int total;
  5.     Solution(vector<int>& w) {
  6.         total = 0;
  7.         for(auto &index : w)
  8.         {
  9.             total += index;
  10.             //这里存放的是每一个Index所占据空间的右开区间
  11.             prob.push_back(total);
  12.         }
  13.     }
  15.     int pickIndex() {
  16.         int randval = rand() % total;
  18.         int lo = 0, hi = prob.size() - 1;
  20.         while(lo != hi)
  21.         {
  22.             int mid = (lo + hi) / 2;
  23.             //由于是右开区间，所以当相等时，对lo赋予mid+1
  24.             if(prob[mid] <= randval)
  25.                 lo = mid + 1;
  26.             else
  27.                 hi = mid;
  28.         }
  30.         return lo;
  31.     }
  32. };
  34. /**
  35.  * Your Solution object will be instantiated and called as such:
  36.  * Solution* obj = new Solution(w);
  37.  * int param_1 = obj->pickIndex();
  38.  */

在上述解法中，rand()生成的仅是伪随机数，下面我们来看看官方给出的解法
想法
让 随机数 - 图1, 其中随机数 - 图2

如果我们从 半开区间 [0,tot)中随机选择一个整数会发生什么？

是否有办法将每一个可能的整数映射到w 中一个下标，使得每个下标映射的数目与下标的权重对应呢？

是否有办法使用少于 O(tot)的空间呢？

算法

求出前缀和数组p，其中随机数 - 图3在范围[0,tot)中随机选择一个整数 targ
使用二分查找来找到下标x，其中x是满足 targ< p[x] 的最小下标。

对于某些下标i，所有满足随机数 - 图4的整数 v都映射到这个下标。因此，所有的下标都与下标权重成比例。

  1. class Solution {
  2. public:
  3.     vector<int> psum;
  4.     int tot = 0;
  5.     //c++11 random integer generation
  6.     mt19937 rng{random_device{}()};
  7.     uniform_int_distribution<int> uni;
  9.     Solution(vector<int> w) {
  10.         for (int x : w) {
  11.             tot += x;
  12.             psum.push_back(tot);
  13.         }
  14.         uni = uniform_int_distribution<int>{0, tot - 1};
  15.     }
  17.     int pickIndex() {
  18.         int targ = uni(rng);
  20.         int lo = 0, hi = psum.size() - 1;
  21.         while (lo != hi) {
  22.             int mid = (lo + hi) / 2;
  23.             if (targ >= psum[mid]) lo = mid + 1;
  24.             else hi = mid;
  25.         }
  26.         return lo;
  27.     }
  28. };

复杂度分析

  • 时间复杂度：O（N）的预处理，priceIndex需要花费O（log(N)）的时间
  • 空间复杂度：O（N）

在评论区中有个评论还比较有意思

Spring Cloud Ribbon （客户端负载均衡）策略中的 WeightedResponseTimeRule

此题可简述为「按权重，看作多个区间，按区间宽度越大，概率越大」

在 Ribbon 相关架构中，服务端给客户端一个服务列表，类似 Map 结构。若客户端想调用 key = serviceA，可选的具体服务端实例有 Set 的 [“/svc/a1”, “/svc/a2”, “/svc/a3”]，由客户端自行决定

Ribbon 作为客户端负载均衡来帮助客户端选择去哪个具体服务实例（a1 / a2 / a3），希望雨露均沾，又希望别运气不好抽到响应慢的服务器，故有了一种根据权重的均衡策略

权重是通过定时统计最近一段时间内，a1 / a2 / a3 各自的访问响应时间如何，如 a1: 10ms，a2: 20ms，a3: 40ms

通过算法（不赘述，有兴趣可留言喔）计算得 a1: [0, 60]，a2: (60, 110]，a3: (110, 140] 的区间对应

下次再需要访问 serviceA 时，随机一个数 [0, 140]，看落在哪个区间，就选那个实例

RabbitMQ 的 Topic 交换器使用 Trie 匹配

MySQL 中的 IN 语法涉及二分算法