栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

Java&C++题解与拓展——leetcode478.在圆内随机生成点【mt19937、uniform

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Java&C++题解与拓展——leetcode478.在圆内随机生成点【mt19937、uniform

每日一题做题记录,参考官方和三叶的题解

目录
  • 题目要求
  • 思路一:模拟(计算分布函数)
    • Java
    • C++
      • STL mt19937
      • STL uniform_real_distribution
  • 思路二:拒绝采样
    • Java
    • C++
    • Rust
  • 总结

题目要求

思路一:模拟(计算分布函数)
  • 用 l e n len len和 a n g ang ang两个值来标记每个随机点,其中 l e n len len表示到圆心的距离, a n g ang ang表示与 x x x轴正向的夹角。
  • 若直接在 [ 0 , r ] [0,r] [0,r]的范围内生成 l e n len len以及 [ 0 , 2 π ) [0,2pi) [0,2π)的范围内生成 a n g ang ang,得到的点是不均匀的。
    • 【这里是我对本题的误解】
  • 在单位圆内随机生成一个点,因为 l e n 与 r 的 比 例 len与r的比例 len与r的比例不等价于 以 l e n 为 半 径 的 圆 面 积 与 总 面 积 的 比 例 以len为半径的圆面积与总面积的比例 以len为半径的圆面积与总面积的比例,所以不能直接在 [ 0 , r ] [0,r] [0,r]内随机。
    • 具体推导过程需要 概 率 密 度 函 数 P D F 概率密度函数PDF 概率密度函数PDF和 累 计 分 布 函 数 C D F 累计分布函数CDF 累计分布函数CDF,因为 概率论忘差不多了 比较难理解就不写了。
    • 概括来说,可以在 [ 0 , r 2 ] [0,r^2] [0,r2]范围内随机再开方,从而确保距离与面积比例一致。
Java
class Solution {
    double r, x, y;
    Random ran = new Random();
    public Solution(double radius, double x_center, double y_center) {
        r = radius;
        x = x_center;
        y = y_center;
    }
    
    public double[] randPoint() {
        double len = Math.sqrt(ran.nextDouble(r * r)), ang = ran.nextDouble(2 * Math.PI);
        double rx = x + len * Math.cos(ang), ry = y + len * Math.sin(ang);
        return new double[]{rx, ry};
    }
}
  • 时间复杂度: O ( 1 ) O(1) O(1)
  • 空间复杂度: O ( 1 ) O(1) O(1)
C++
class Solution {
    double r, x, y;
    mt19937 gen{random_device{}()};
    uniform_real_distribution dis;
public:
    Solution(double radius, double x_center, double y_center) : dis(0, 1), r(radius), x(x_center), y(y_center) {}
    
    vector randPoint() {
        double len = sqrt(dis(gen)), ang = dis(gen) * 2 * acos(-1.0);
        double rx = x + len * cos(ang) * r, ry = y + len * sin(ang) * r;
        return {rx, ry};
    }
};
  • 时间复杂度: O ( 1 ) O(1) O(1)
  • 空间复杂度: O ( 1 ) O(1) O(1)
STL mt19937
  • 学习参考链接
  • 一个伪随机数产生器,返回无符号整数(unsigned int)。
STL uniform_real_distribution
  • 学习参考链接
  • 连续均匀分布类模板,定义了一个默认返回double型浮点数的连续分布,返回值半开放(不含上界)。
  • 类似的还有uniform_int_distribution。
思路二:拒绝采样
  • 就是先在一个简单的范围(如矩形范围)内生成随机数,然后判断拒绝掉不在题设范围内的数;
  • 本题就在边长为 2 R 2R 2R的正方形内生成随机数,然后拒绝四个角角上的那一点。

由于正方形的面积为 ( 2 R ) 2 = 4 R 2 (2R)^2=4R^2 (2R)2=4R2,圆的面积为 π R 2 pi R^2 πR2,因此在正方形中随机生成的点落在圆内的概率为 P r ( ⋅ ) = π R 2 4 R 2 ≈ 0.785 Pr(cdot)=frac{pi R^2}{4R^2}approx0.785 Pr(⋅)=4R2πR2​≈0.785,期望的生成次数为 E ( ⋅ ) = 1 0.785 ≈ 1.274 = O ( 1 ) E(cdot)=frac{1}{0.785}approx1.274=O(1) E(⋅)=0.7851​≈1.274=O(1)。

Java
class Solution {
    Random ran = new Random();
    double r, x, y;
    public Solution(double radius, double x_center, double y_center) {
        r = radius;
        x = x_center;
        y = y_center;
    }
    
    public double[] randPoint() {
        while(true) {
            double rx = ran.nextDouble() * (2 * r) - r;
            double ry = ran.nextDouble() * (2 * r) - r;
            if(rx * rx + ry * ry <= r * r) {
                return new double[]{x + rx, y + ry};
            }
        }
    }
}
  • 时间复杂度:期望时间复杂度为 O ( 1 ) O(1) O(1)
  • 空间复杂度: O ( 1 ) O(1) O(1)
C++
class Solution {
    double r, x, y;
    mt19937 gen{random_device{}()};
    uniform_real_distribution dis;
public:
    Solution(double radius, double x_center, double y_center) : dis(-radius, radius), r(radius), x(x_center), y(y_center) {}
    
    vector randPoint() {
        while (true) {
            double rx = dis(gen), ry = dis(gen);
            if(rx * rx + ry * ry <= r * r) {
                return {x + rx, y + ry};
            }
        }
    }
};
  • 时间复杂度:期望时间复杂度为 O ( 1 ) O(1) O(1)
  • 空间复杂度: O ( 1 ) O(1) O(1)
Rust
struct Solution {
    r:f64,
    x:f64,
    y:f64,
    rr:f64,
}

impl Solution {

    fn new(radius: f64, x_center: f64, y_center: f64) -> Self {
        Solution {r:radius, x:x_center, y:y_center, rr:radius * radius}
    }
    
    fn rand_point(&self) -> Vec {
        use rand::{thread_rng, Rng};
        let mut rng = thread_rng();
        let (rx,ry) = loop {
            let (rx,ry) = (rng.gen_range(-self.r, self.r), rng.gen_range(-self.r, self.r));
            if rx * rx + ry * ry <= self.rr {
                break (rx,ry);
            }
        };
        vec![rx + self.x, ry + self.y]
    }
}
  • 时间复杂度:期望时间复杂度为 O ( 1 ) O(1) O(1)
  • 空间复杂度: O ( 1 ) O(1) O(1)
总结

本来以为是个简单模拟题,结果题解一波分析很是高深,仿佛回到了高数课堂。倒是学习了C++的随机浮点数生成,前几天生套rand()通不过的问题得到了解答。


欢迎指正与讨论!
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/952535.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号