按权重随机选择

难度:

标签:

题目描述

English description is not available for the problem. Please switch to Chinese.

代码结果

运行时间: 99 ms, 内存: 20.9 MB

/*
 * 思路：
 * 和Java版本一样，我们需要构建一个前缀和数组prefixSums。
 * 不同之处在于我们将尽量使用Java Stream来构建前缀和数组。
 */
import java.util.*;
import java.util.stream.IntStream;

class Solution {
    private int[] prefixSums;
    private Random random;

    public Solution(int[] w) {
        prefixSums = new int[w.length];
        prefixSums[0] = w[0];
        IntStream.range(1, w.length).forEach(i -> prefixSums[i] = prefixSums[i - 1] + w[i]);
        random = new Random();
    }

    public int pickIndex() {
        int target = random.nextInt(prefixSums[prefixSums.length - 1]) + 1;
        return IntStream.range(0, prefixSums.length)
                        .filter(i -> prefixSums[i] >= target)
                        .findFirst()
                        .orElse(-1);
    }
}

解释

方法:

此题解采用了前缀和和二分搜索的方法来解决问题。首先，将输入权重数组转换为一个概率数组，该数组的每个元素表示从开始到当前位置的权重和占总权重的比例。具体操作是，在初始化函数中计算总权重，并构建一个概率数组，其中每个元素是到当前元素为止的权重和除以总权重。在pickIndex函数中，使用random.random()生成一个[0, 1)之间的随机数，然后通过二分搜索（bisect_left）找到这个随机数应该插入概率数组的位置，由于概率数组是累积的，这样可以保证按权重随机选择下标。

时间复杂度:

O(log n)

空间复杂度:

O(n)

代码细节讲解

🦆

在初始化时，你创建了概率数组`self.prob`，它的第一个元素为0是出于什么考虑？

▷

在初始化概率数组时，第一个元素设置为0是为了配合二分搜索算法的使用。这种设置使得概率数组成为一个从0开始，逐渐增加直到1的数组。由于random.random()生成的随机数范围是[0, 1)，第一个元素为0可以确保即使随机数非常小（接近0），二分搜索也能正确找到第一个大于或等于这个随机数的位置。这保证了在边界情况下，返回的索引能够正确反映权重数组中第一个元素的权重。

🦆

在构建概率数组时，将每个权重加到`temp`并更新`self.prob`，这种方法是否保证了概率分布正确反映权重的累积特性？

▷

是的，这种方法确保了概率分布正确地反映了权重的累积特性。通过逐个添加权重到`temp`并将其除以总权重来更新`self.prob`，我们逐步构建了一个累积概率数组。这个累积概率数组表示从第一个元素到当前元素的权重和占总权重的比例。因此，每个元素在概率数组中的位置正比于其权重，从而确保了按权重的随机选择是公正的。

🦆

函数`pickIndex`中使用`random.random()`生成的随机数代表什么含义，它与权重分布的关系是怎样的？

▷

在`pickIndex`函数中，使用`random.random()`生成的随机数代表在[0, 1)区间内的一个随机实数。这个随机数用来模拟均匀分布的随机事件，其用途是从按权重设置的概率分布中选择索引。通过将这个随机数与累积的概率数组进行比较，我们可以通过二分搜索找到第一个大于或等于这个随机数的概率值的位置。这使得返回的索引的概率与其相应权重成正比，从而确保了按权重的随机选择。换言之，权重越大的元素，其累积概率区间也越大，因此被随机选中的概率也越高。

按权重随机选择

题目描述

代码结果

解释

代码细节讲解

相关问题