随机数
前言
本文记录我学习随机数专题的笔记,包括蓄水池采样,轮盘赌算法,拒绝采样等知识。
分析
集合中取随机 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] 交换即可
效率
时间复杂度:
空间复杂度:
代码
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; } };时间复杂度:,空间复杂度:
蓄水池抽样
每次从 [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; } };时间复杂度:,空间复杂度:
398. 随机数索引
题意
给定一个可能含有重复元素的整数数组,要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。
分析
虽然数据是给定了,但是值为 target 的个数却不固定(不让开空间提前预处理)。那么就只能视为数目不固定求随机数了,那么,我们扫描数组,无视不为 target 的数,就是一个典型的数据增加求随机数的题型。
故直接蓄水池抽样即可
效率
时间复杂度:
空间复杂度:
代码
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 了
效率
时间复杂度:
空间复杂度:
代码
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,不然计算范围会比较麻烦。然后再到前缀和找范围,可以二分。效率
时间复杂度:
空间复杂度:
代码
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 的值
效率
时间复杂度:
空间复杂度:
代码
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 小即可
效率
时间复杂度:
空间复杂度:
代码
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) 中就删掉,然后找需要映射的白名单,从后面往前找比较方便,遇到黑名单跳过,直到找到白名单即可,然后再映射。
效率
时间复杂度:
空间复杂度:
代码
拒绝采样
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; } };
总结
随机数的题型不多,题也很少,不过在实际编程中我们用得还是很多的,虽然很多时候都只是调库,而在面试中,蓄水池抽样和拒绝采样的出现频率也不低,需要好好掌握才行。


