C 随机不重复元素~转
2024-08-30 21:59:27
随机产生不重复元素:如何高效产生m个n范围内的不重复随机数(m<=n)
如何产生不重复的随机数?最容易想到的方法,是逐个产生这些随机数,每产生一个,都跟前面的随机数比较,如果重复,就重新产生。这是个很笨的方法,且比较次数呈线性增长,越往后次数越多。其实这些比较是多余的,完全可以不进行比较,只要反过来,按顺序产生这些数,但随机产生它们的位置。例如下面产生100个100以内不重复随机数的代码:
int a[100];
for(i=0; i<=99; ++i) a[i]=i;
for(i=99; i>=1; --i) swap(a[i], a[rand()%i]);
上面这段代码只需要遍历一次就可以产生这100个不重复的随机数,它是如何做到的呢?首先第二行按顺序用0到99填满整个数组;第三行,是随机产生从0到m-2个数组下标,把这个下标的元素值跟m-1下标的元素值交换,一直进行到下标为1的元素。因此它只需要遍历一次就能产生全部的随机数。
再看下面的代码,原理跟上面例子相似,但效率比上面的差点,但仍不失为一个好方法:
int a[100]={0};
int i, m;
for(i=1; i<=99; ++i)
{
while(a[m=rand()%100]);
a[m] = i;
}
这段代码也是随机产生位置,但它预先把整个数组初始化为0,然后随机产生其中一个位置,如果该元素值为0,表示这个位置还没有被使用过,就把i赋予它;否则,就重新随机产生另一个位置,直到整个数组
被填满。这个方法,越到后面,遇到已使用过的元素的可能性越高,重复次数就越多,这是不及第一个方法的地方,但总的来说,效率还是不错的。
最新文章
- JPush API client library for C Sharp(极光推送API)
- php 5.4 5.5 如何连接 ms sqlserver
- 295.	Find Median from Data Stream
- ios 沙盒 NSCoding(相当于JAVA对象序列化) 归档 数据存储
- WINDOWS自启动程序的10大隐身之所
- SQL Server 数据的创建、增长、收缩
- as3 与js相互通信
- MVC是一种用于表示层设计的复合设计模式
- <;hdu - 1863>; 畅通工程 并查集和最小生成树问题
- Maven搭建springMVC+spring+hibernate环境
- shell 之awk 关联数组高级应用
- javase基础回顾(四) 自定义注解与反射
- Adobe After Effect CC2017 for Mac
- vue初体验
- 获取CPU ID--查看CPU数量/核数
- Unicode转字符串
- oracle-sql优化器
- 1. orcle 创建可扩展表空间
- LINUX分辨率修改
- dedecms提取某栏目及子栏目名称到首页怎么弄