1. 题目

原题链接

给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标
i 的概率与 w[i] 成正比。

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

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

Related Topics 二分查找 Random
👍 100 👎 0

2. 题解

2.1 解法1: 前缀和 + 二分查找

主要思路

• 对于 w[i][1,3,5,6], 计算其累计的前缀和数组为: [1,4,9,15]
• 然后使用Random产生一个[1,15]之间的随机数，
  如果随机数落在[1,1]，应该找到的值为 1, 对应元素下标为0，
  如果随机数落在[2,4]区间，应该找到值 4, 对应元素下标为1，
  如果随机数落在[5,9]区间，应该找到值 9, 对应元素下标为2，
  如果随机数落在[10,15]，应该找到值 15, 对应元素下标为3，
• 如果使用顺序遍历来查找元素效率较低, 由于前缀和数组是有序的, 所以可以使用二分法查找
• 注意: 需要先确定需要查找的元素在数组中的位置 , 当前根据题意, 要查找的元素应该是 找到第一个 >= target 的值的元素, 确定了这一点才能写出正确的二分查找, 在确定时, 建议多举例尝试几个数, 来保证目标元素定义的正确性!

    class Solution {int[] pres;int sum = 0;Random random;public Solution(int[] w) {pres = new int[w.length];random = new Random();for (int i = 0; i < pres.length; i++) {sum += w[i];pres[i] = sum;}}public int pickIndex() {// 生成随机数, 1 到 sum 的整数, [1,sum]int target = random.nextInt(sum) + 1;//target = 2;// 找到第一个 >= target 的值int left = 0, right = pres.length - 1;while (left < right) {int mid = left + right >> 1;if (pres[mid] >= target) {right = mid;} else {left = mid + 1;}}return left;}}

3. 实战场景补充

• Spring Cloud Ribbon （客户端负载均衡）策略中的``WeightedResponseTimeRule`
  • 此题可简述为「按权重，看作多个区间，按区间宽度越大，概率越大」
  • 在 Ribbon 相关架构中，服务端给客户端一个服务列表，类似 Map<String, Set<String>> 结构。若客户端想调用 key = serviceA，可选的具体服务端实例有 Set<String> 的 ["/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 语法涉及二分算法

参考:
Java 二分法
官方题解