选择一个随机矩形但按面积加权：

在用 Leetcode 做一些练习时，我遇到了一个问题，需要从一组不重叠的矩形中选择内部的随机整数点（ https://leetcode.com/problems/random-point-in-non-overlapping -矩形/描述/ )。虽然选择随机整数点有点微不足道，但问题要求点选择在所有矩形的整个区域中具有相同的可能性。

我提出的解决方案是随机选择一个矩形，但对区域和区域进行加权，从内部随机选择整数点。在 python 中，我一直在使用以下代码：

# select one rectangle randomly but weighting rectangles areas
selected = 0
total_area = self.rects_area[0]

for i in range(1, len(self.rects_area)):
    total_area += self.rects_area[i]
    selected = i if random() <= self.rects_area[i] / total_area else selected

with:

- rects: List[List[int]], with rects[i] = [ai, bi, xi, yi], (ai, bi) -> bottom left and (xi,yi) -> top right
- rects_area List[int]: area of each rects[i] using the same indexing

我通过了 35 个测试中的 31 个，但最后 4 个似乎考虑了分布。所以，我的问题是最后一行（selected = i if...）是否确实随机选择了一个矩形，但根据大小加权。我得到的见解来自一个著名的问题，在这个问题中，你必须从一个流中随机选择数字，而你不知道会出现多少个数字。第一个是 1/1，第二个是 1/2，第三个是 1/3，依此类推，所以我将其调整为使用面积作为分子，并将到该点的总面积作为分母。那么，对于 3 个三角形面积：2,3 和 5，概率将为 2/2、3/5 和 5/7。

有什么建议吗？

你的逻辑在随机选择加权矩形方面几乎是正确的，但有一个小错误。问题在于，你每次迭代都会更新 selected ，这并不符合概率分布。你应该更新 selected 的概率仅在当前矩形的加权面积大于随机数时才成立。

以下是用 Python 修正代码的方法：

# 选择一个随机矩形，但对矩形面积进行加权
selected = 0
total_area = self.rects_area[0]

for i in range(1, len(self.rects_area)):
    total_area += self.rects_area[i]
    # 仅当随机数小于或等于加权概率时才更新 selected
    if random() < self.rects_area[i] / total_area: 
        selected = i 

以下是你的代码工作原理以及我们如何改进它的细分：

1. 初始化：

2. 你正确地初始化了 selected = 0 和 total_area 为第一个矩形的面积。

3. 迭代矩形：

4. 你遍历了从第二个矩形开始的矩形列表。

5. 在每次迭代中，你都正确地更新了 total_area 。

6. 加权选择（需要修正的地方）：

7. 你最初的条件 random() <= self.rects_area[i] / total_area 在逻辑上存在缺陷。你不能在每次迭代中都更新 selected 。你应该更新 selected 的概率仅在当前矩形的加权面积大于随机数时才成立。

通过仅当随机数落在当前矩形的加权概率范围内时才更新 selected ，你确保了选择过程准确地反映了每个矩形的面积。

此修正后的代码将根据其面积正确地随机选择一个矩形，从而解决你遇到的分布问题。