随机数专题总结

2022.03.17

发布于未知归属地

拒绝采样 C++蓄水池抽样随机学习分享

随机数

前言

本文记录我学习随机数专题的笔记，包括蓄水池采样，轮盘赌算法，拒绝采样等知识。

分析

集合中取随机 m 个数

如果数据集提前固定了，那么直接编号，再取随机数即可
如果数据集固定，且有权重，要按权重来抽取，那么就把权重计算前缀和，再取随机数，最后二分看在那个区间
如果数据集不固定，可能随时增加，这时就采用蓄水池抽样算法

直接随机数

最简单的，就是标号，然后取随机数，比如取随机取数组中的元素，比如在此基础上用于打乱数组的洗牌算法，就是这个原理

公式

要取得 [a,b) 的随机整数，使用 (rand () % (b-a))+ a;

要取得 [a,b] 的随机整数，使用 (rand () % (b-a+1))+ a;

要取得 (a,b] 的随机整数，使用 (rand () % (b-a))+ a + 1;

通用公式 a + rand () % n；其中的 a 是起始值，n 是整数的范围。

要取得 a 到 b 之间的随机整数，另一种表示：a + (int) b * rand () / (RAND_MAX + 1)。

要取得 0～1 之间的浮点数，可以使用 rand () /double (RAND_MAX)。

洗牌算法

洗牌算法用于打乱数组，stl 的 shuffle 函数就是这个原理，非常简单：

给定数组 data，范围为 [0,n)，我们遍历 data，当遍历到下标为 i 的元素时
从后面所有元素 [i+1,n) 中，随机取一个数 data[j] 和当前元素 data[i] 交换即可
而从 [i+1,n) 中随机取一个元素，就是直接先从 [0,n-i) 取一个随机数，再加 i 即可

for (int i=0;i<n;i++) {
	int j=i+rand()%(n-i);
	swap(nums[i],nums[j]);
}

权重、轮盘赌、彩票算法

所谓的轮盘赌算法、彩票算法等，是指给一个数组，每个数都有一定的权值，然后按权值概率随机返回数。是很常见的算法之一，比如进程调度中按权重调度就是这个原理。

方法也很简单，就是古典分布，画个线段，每个数分权重大小的距离，然后随机取点，再哪个区间就是哪个数。

具体实现就是先前缀和（不前插入 0），然后二分（或遍历）找到对应的区间即可

for (int i=1;i<n;i++) {
	pre[i]+=pre[i-1];
}

int l=0;
int r=n-1;
int mid;

while(l<r) {
	mid = (r-l)/2;

	if (pre[i]<=target) {
		l=mid+1;
	} else {
		r=mid
	}

return l;

蓄水池抽样

蓄水池抽样算法，用于数据集在变化时随机抽取数，原理其实很简单，假如我们每次从数据集中随机抽取一个元素，刚开始时，数据集中元素个数为 1，则：

数据集中元素个数为 1 时，抽取一个元素的概率为 1
数据集新增一个元素，现在总元素个数为 2，则抽取一个元素的概率为 0.5
数据集新增一个元素，现在总元素个数为 3，则抽取一个元素的概率为 0.33
...

当现在数据集中个数为 i，要抽取的个数为 1 个，则抽取概率为 1/i，如果抽取个数为 m 个，则抽取概率为 m/i，就是一个简单的古典几何分布问题。

从数据集合 data 中随机抽取 m 个数，算法步骤如下：

建立大小为 m 的蓄水池
遍历 data，如果蓄水池大小小于 m，直接放入水池中
否则，假设现在是第 i 个数(i>m)，那么从 [0,i] 中选一个随机数 t，如果 t<m，则把蓄水池中第 t 个元素替换为当前元素 data[i]
最终，蓄水池中的元素就是要求得的元素

#include <bits/stdc++.h>

using namespace std;

vector<int> get(vector<int> data, int m) {
    vector<int> res;

    for (int i = 0; i < data.size(); i++) {
        if (i < m) {
            res.push_back(data[i]);
            continue;
        }

        int t = rand() % i;
        if (t < m) {
            res[t] = data[i];
        }
    }

    return res;
}

int main() {
    srand((unsigned) time(NULL));

    vector<int> data(10000);
    for (int i = 0; i < 10000; i++) {
        data[i] = i;
    }

    const vector<int> &res = get(data, 10);
    for (const auto &item : res) {
        cout << item << endl;
    }

    return 0;
}

拒绝采样

拒绝采样主要用在已知一个范围随机数生成器，求另一个范围的随机数生成器题型上，即已知 randx 求 randy 问题，比如典型的 rand7 求 rand10 问题.

所谓的拒绝采样，就是指加入我们有一个 randx，要生成 randy，且 y<x，那么直接调用 randx，判断和 y 大大小关系，大于 y 就直接舍弃掉，否则直接返回。

最终从外部来看，randy 是概率的，只是 y 越小，调用时间就越久，期望值就越低.

常见形式

i=randx()
while(i<?) { // 或者 i>? 等等，要看具体范围，最后可能还需要对这些数进行计算
	i=randx()
}
return i;

常用公式有 (randX () - 1)*Y + randY () → [1, X * Y]

题型

随机数

list

384. 打乱数组

题意

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。

分析

使用洗牌算法，遍历数组，假设当前坐标为 i，则从后面的元素 [i,size) 中随机取一个元素和 nums[i] 交换即可

效率

时间复杂度： $O (n)$

空间复杂度： $O (1)$

代码

class Solution {
    vector<int> n;

public:
    Solution(vector<int>& nums) {
        n=nums;    
    }
    
    vector<int> reset() {
        return n;
    }
    
    vector<int> shuffle() {
        vector<int> m(n.begin(),n.end());

        for (int i=0;i<m.size();i++){
            int j=i+rand()%(m.size()-i);
            swap(m[i],m[j]);
        }

        return m;
    }
};

蓄水池抽样

list

382. 链表随机节点

题意

给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。

暴力

编号然后取随机数

class Solution {
public:
    int length=0;
    ListNode *h,*cur;
    
    Solution(ListNode* head) {
        h=head;
        while(head){
            head=head->next;
            length++;
        }
    }
    
    int getRandom() {
        int n=random()%length;
        cur=h;
        // cout<<n<<endl;  
        // cout<<endl;
        while(n--){
            cur=cur->next;
        }
        // cout<<cur->val<<endl;
        return cur->val;
    }
};

时间复杂度： $O (n)$ ，空间复杂度： $O (1)$

蓄水池抽样

每次从 [0,i) 中取随机数，如果取到 0，则结果更新

class Solution {
    ListNode *h;

public:
    Solution(ListNode* head) {
        h=head;
    }
    
    int getRandom() {
        int res=h->val;
        ListNode *cur=h;
        int i=1;

        while(cur){
            // [0,i) 中选，如果选到 0，则交换
            int t=rand()%i;
            if (t==0){
                res=cur->val;
            }
            i++;
            cur=cur->next;
        }
        
        return res;
    }
};

时间复杂度： $O (n)$ ，空间复杂度： $O (1)$

398. 随机数索引

题意

给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。您可以假设给定的数字一定存在于数组中。

分析

虽然数据是给定了，但是值为 target 的个数却不固定（不让开空间提前预处理）。那么就只能视为数目不固定求随机数了，那么，我们扫描数组，无视不为 target 的数，就是一个典型的数据增加求随机数的题型。

故直接蓄水池抽样即可

效率

时间复杂度： $O (n)$

空间复杂度： $O (1)$

代码

class Solution {
    vector<int> n;

public:
    Solution(vector<int>& nums) {
        n=nums;
    }
    
    int pick(int target) {
        int res=0;
// cnt 为 0
        int cnt=0;

        for (int i=0;i<n.size();i++){
            if (n[i]==target){
                cnt++;
// 从 [0,cnt) 中取随机数
                int t=rand()%cnt;
                if (t==0){
                    res=i;
                }
            }
        }

        return res;
    }
};

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

519. 随机翻转矩阵

题意

• int[] flip() 返回一个满足 matrix[i][j] == 0 的随机下标 [i, j] ，并将其对应格子中的值变为 1

分析

每次随机选，选了之后数就不固定了，故可以蓄水池采样，每次扫描选取(虽然 tle 了

效率

时间复杂度： $O (n)$

空间复杂度： $O (1)$

代码

class Solution {
    vector<vector<int>> nums;
    int col,row;

public:
    Solution(int m, int n) {
        row=m;
        col=n;
        nums=vector<vector<int>> (m,vector<int>(n));
    }
    
    vector<int> flip() {
        int cnt=0;
        int x,y;

        for (int i=0;i<nums.size();i++){
            for (int j=0;j<nums[0].size();j++){
                if (nums[i][j]==1){
                    continue;
                }

                cnt++;

                if (rand()%cnt ==0){
                    x=i;
                    y=j;
                }
            }
        }

        nums[x][y]=1;

        return {x,y};
    }
    
    void reset() {
        nums=vector<vector<int>> (row,vector<int>(col));
    }
};

轮盘赌

list

528. 按权重随机选择

题意

请你实现一个函数 pickIndex ，它可以随机地从范围 [0, w.length - 1] 内（含 0 和 w.length - 1）选出并返回一个下标。选取下标 i 的概率为 w[i] / sum(w) 。

分析

就是几何分别，开一个总长为 sum 的线段，然后划分长度给对应的数，再随机选数，看落在哪个线段中，就选哪个数。

具体的实现的话，就是对数组求前缀和，然后对总和范围内取随机数，再看落在哪个范围。需要注意：前缀和不需要再前面插入 0 ，不然计算范围会比较麻烦。然后再到前缀和找范围，可以二分。

效率

时间复杂度： $O (n)$

空间复杂度： $O (1)$

代码

class Solution {
    vector<int> pre;

public:
    Solution(vector<int>& w) {
        for (int i=1;i<w.size();i++){
            w[i]=w[i]+w[i-1];
        }
        pre=w;
    }
    
    int pickIndex() {
        int i=rand()%pre[pre.size()-1]+1;
        int l=0;
        int r=pre.size()-1;
        int mid;

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

            if (pre[mid]<i){
                l=mid+1;
            } else {
                r=mid;
            }
        }

        return l;
    }
};

拒绝采样

list

470. 用 Rand7 () 实现 Rand10 ()

题意

给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。

分析

先使用拒绝采用生成 rand2(1-2)，和 rand5(1-5)，然后根据 rand2 的结果判断奇偶性，是奇数生成 1-5，偶数生成 5-10，然后再返回 rand5 的值或 5+rand5 的值

效率

时间复杂度： $O (n)$

空间复杂度： $O (1)$

代码

class Solution {
public:
    int rand10() {
        int n2,n5;

        // rand2
        while((n2=rand7())>2){};

        // rand5
        while((n5=rand7())>5){};

        if (n2%2==0){
            return n5;
        }

        return n5+5;
    }
};

478. 在圆内随机生成点

题意

给定圆的半径和圆心的位置，实现函数 randPoint ，在圆中产生均匀随机点。

分析

在圆的外接正方形中生成随机坐标，然后判断是否在园内，不在就拒绝掉。

具体实现，就是在固定正方向最左下脚的点 (x-r,y-r)，然后生成 [0,2r] 的随机浮点数，再用两点距离 (x-x1)(x-x1)+(y-y1)(y-y1) 判断是否比 r 小即可

效率

时间复杂度： $O (n)$

空间复杂度： $O (1)$

代码

class Solution {
    double r,x,y;

public:
    Solution(double radius, double x_center, double y_center) {
        r=radius;
        x=x_center;
        y=y_center;
    }
    
    vector<double> randPoint() {
        while(true){
            double x1=x-r+(double(rand()) / RAND_MAX * r * 2);
            double y1=y-r+(double(rand()) / RAND_MAX * r * 2);
            double l=sqrt((x1-x)*(x1-x)+(y1-y)*(y1-y));
            if (l<=r){
                return {x1,y1};
            }
        }
    }
};

710. 黑名单中的随机数

题意

给定一个整数 n 和一个无重复黑名单整数数组 blacklist 。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个未加入黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有同等的可能性被返回。

分析

最简单的，自然是直接在 [0,n) 里随机选数，然后如果是黑名单中的，拒绝采样即可，不过这样会 tle。

由于数在黑白名单中是不连续的，所以我们随机取数时非常不方便，那么有没有办法，把白名单的数弄到一个连续的范围，那样我们一次 rand 就能得到结果。

办法也很简单，给定的数范围是 [0,n)，黑名单数组也给了，假设去除掉黑名单，白名单的数总个数为 size 个。那么，如果我们采用一定的办法，把白名单中的数都映射到 [0,size) 中，那么我们 rand()%size 就能一次得到结果。

现在，给定的范围被分成了 [0,size),[size,n) 两个区间，我们要把白名单中的数映射到 [0,size) 中，那么原先在 [0,size) 中的就不用管了，在 [size,n) 里黑名单的数也不用管了。

所以，我们的办法，就是把 [size,n) 中的白名单数映射到 [0,size) 黑名单中，有人可能会问，如果两个数量不匹配呢？

当然这是不可能的，因为 size 就是白名单个数，所以一定能全部映射过来。

故我们遍历黑名单的数，如果是 [size,n) 中就删掉，然后找需要映射的白名单，从后面往前找比较方便，遇到黑名单跳过，直到找到白名单即可，然后再映射。

无效的图片地址

效率

时间复杂度： $O (n)$

空间复杂度： $O (1)$

代码

拒绝采样

class Solution {
    unordered_set<int> s;
    int size;

public:
    Solution(int n, vector<int>& blacklist) {
        size=n;                
        for (auto i:blacklist){
            s.insert(i);
        }
    }
    
    int pick() {
        int x=random()%size;
        while(s.find(x)!=s.end()){
            x=random()%size;
        }
        return x;
    }
};

黑名单映射

class Solution {
    int size;
    // [0,size) 区间的黑名单 -> [size,n) 区间的白名单
    unordered_map<int,int> m;

public:
    Solution(int n, vector<int>& blacklist) {
        size=n-blacklist.size();
        int j=n-1;
        unordered_set<int> s;

        for (auto i:blacklist){
            s.insert(i);
        }

        for (auto i:blacklist){
            // 如果是 [size,n) 区间的黑名单，则跳过
            if (i>=size){
                continue;
            }

            // 注意，j 是从最后开始扫描的，在 [size,n) 范围中，需要从最后开始找白名单
            while (s.find(j)!=s.end()){
                j--;
            }

            m[i]=j;
            j--;
        }
    }
    
    int pick() {
        int i=random()%size;
        if (m.find(i)!=m.end()){
            return m[i];
        }
        return i;
    }
};

总结

随机数的题型不多，题也很少，不过在实际编程中我们用得还是很多的，虽然很多时候都只是调库，而在面试中，蓄水池抽样和拒绝采样的出现频率也不低，需要好好掌握才行。

参考

蓄水池抽样算法（Reservoir Sampling）