LeetCode 497. 非重叠矩形中的随机点

约 6 分钟
文章信息 6 个分类 7 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 华为
标签
数组 数学 二分查找 前缀和 有序集合 随机化 水塘抽样

题目描述

✅ 497. 非重叠矩形中的随机点

image-20260929100727738

image-20260929100727903

image-20260929100727970

题意分析

给定若干互不重叠、边平行于坐标轴的矩形，每次从它们覆盖的所有整数坐标点中等概率返回一个点，边界上的点也算在内。等概率针对每个点，而不是每个矩形。

解法：格点前缀计数 + 二分采样

核心思路

[!blue]

为所有格点分配从 1 到 total 的连续编号，再均匀抽一个编号。矩形 [x1, y1, x2, y2] 横向有 x2 - x1 + 1 个整数坐标，纵向有 y2 - y1 + 1 个，所以包含两者乘积个格点。矩形互不重叠，所有格点都能获得唯一编号。

用 prefix[i] 保存前 i + 1 个矩形的格点总数。第 i 个矩形占据编号 prefix[i - 1] + 1 到 prefix[i]，第一个矩形从 1 开始。随机取得 k 后，二分第一个 prefix[i] >= k 的位置，就找到了它所属的矩形；较大矩形占据更多编号，自然会按格点数获得更高的选中概率。

设此前矩形共有 base 个点，当前矩形内的零起始偏移为 offset = k - base - 1。按列排列格点，每列有 height 个点，所以 offset / height 是第几列，offset % height 是列内第几个点；加上左下角坐标即可还原结果。

这个商余映射在矩形内部是一一对应的，且所有编号被均匀抽取，因此每个格点恰好以 1 / total 的概率返回，无需分别再随机选择横、纵坐标。

解题步骤

  1. 构造时累计每个矩形的格点数，保存 64 位前缀和 prefix 和总点数 total。
  2. 调用有界整数随机接口，在 [1, total] 中均匀取得编号 k。
  3. 二分第一个前缀和不小于 k 的下标；中点满足条件就向左收缩，否则排除中点及左侧。
  4. 计算此前点数 base 和内部偏移 offset = k - base - 1。
  5. 返回 x1 + offset / height、y1 + offset % height。

代码实现

class Solution {
    private final int[][] rects;
    private final long[] prefix;
    private final long total;

    public Solution(int[][] rects) {
        this.rects = rects;
        this.prefix = new long[rects.length];
        long count = 0;

        for (int i = 0; i < rects.length; i++) {
            int[] r = rects[i];
            long width = (long) r[2] - r[0] + 1;
            long height = (long) r[3] - r[1] + 1;

            count += width * height;
            prefix[i] = count;
        }

        this.total = count;
    }

    public int[] pick() {
        // 在全部格点编号中均匀抽样，矩形概率自然与点数成正比。
        long k = java.util.concurrent.ThreadLocalRandom.current().nextLong(total) + 1;
        int idx = lowerBound(prefix, k);
        int[] r = rects[idx];
        long height = (long) r[3] - r[1] + 1;

        long base = idx == 0 ? 0 : prefix[idx - 1];
        // 整体编号从一开始，矩形内部偏移转换为从零开始。
        long offset = k - base - 1;
        // 按列展开：商是横向偏移，余数是纵向偏移。
        int x = (int) (r[0] + offset / height);
        int y = (int) (r[1] + offset % height);

        return new int[] {
            x,
            y
        };
    }

    private int lowerBound(long[] arr, long target) {
        int l = 0;
        int r = arr.length;

        while (l < r) {
            int m = l + (r - l) / 2;

            if (arr[m] >= target) {
                r = m;
            } else {
                l = m + 1;
            }
        }

        return l;
    }
}

import "math/rand"

type Solution struct {
    rects  [][]int
    prefix []int64
    total  int64
}

func Constructor(rects [][]int) Solution {
    prefix := make([]int64, len(rects))
    var total int64
    for i, r := range rects {
        width := int64(r[2]) - int64(r[0]) + 1
        height := int64(r[3]) - int64(r[1]) + 1
        total += width * height
        prefix[i] = total
    }
    return Solution{rects: rects, prefix: prefix, total: total}
}

func (this *Solution) Pick() []int {
    // 在全部格点编号中均匀抽样，矩形概率自然与点数成正比。
    k := rand.Int63n(this.total) + 1
    idx := lowerBound(this.prefix, k)
    r := this.rects[idx]
    height := int64(r[3]) - int64(r[1]) + 1

    var base int64
    if idx > 0 {
        base = this.prefix[idx-1]
    }
    // 整体编号从一开始，矩形内部偏移转换为从零开始。
    offset := k - base - 1
    // 按列展开：商是横向偏移，余数是纵向偏移。
    x := r[0] + int(offset/height)
    y := r[1] + int(offset%height)
    return []int{
        x,
        y,
    }
}

func lowerBound(arr []int64, target int64) int {
    l, r := 0, len(arr)
    for l < r {
        m := l + (r-l)/2
        if arr[m] >= target {
            r = m
        } else {
            l = m + 1
        }
    }
    return l
}

复杂度分析

  • 时间复杂度：构造为 $O(R)$，单次采样期望为 $O(\log(R+1))$，其中 R 为矩形数；随机编号后只需一次二分及常数次坐标计算。
  • 空间复杂度：$O(R)$，保存前缀点数，不展开全部格点。

关键点总结

[!green]

  • 均匀的是最终格点，不是矩形编号。
  • 闭区间每个方向都要加一。
  • 随机编号、下界比较与内部偏移必须使用同一套起始约定。

易错点总结

[!yellow]

  • 等概率选矩形再选点：不同大小矩形中的点概率不同。
  • 点数漏掉加一：单点或线段矩形可能被算成零容量。
  • 下界使用严格大于：矩形最后一个编号归属错误。
  • 除数与坐标方向混用：商和余数可能产生越界坐标。

相似题目

题目 难度 关联与区别
528. 按权重随机选择 中等 先按每个矩形包含的整数点数量加权选择区域，再在区域内均匀选点。
478. 在圆内随机生成点 中等 本题是离散格点，矩形点数包含边界所以边长需加1；圆内采样则针对连续面积。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/60675234
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！