算法一:
用一个List保存所有候选的整数,依次 生成一个随机索引(该索引的范围需要递减),返回该元素,并移除该索引对应的元素值。(缺点
:该算法经测试大概1M 的整数范围需要用到约16M 的内存空间,所以对于
大数据范围,多线程且每个线程分别独立生成不重复的随机整数 的情况下不太适用。
优点
:该算法的可读性最强;而且因为会移除返回的元素,所以占用的内存会动态逐渐减少。)
所以此处没有给出代码示例。
算法二:
用一个数组保存所有候选的整数,依次 生成一个随机索引(该索引的范围需要递减),返回该元素,并 将末尾元素赋值到索引位置
且将原末尾元素位置前一个元素作为新的末尾元素。(缺点
:可读性比上面的算法弱一点;占用内存一直不变。
优点
:该算法经测试大概 1M 的整数范围需要用到约 4M
的内存空间(因为一个int数据占用4个Byte),比上面的算法好一点;时间复杂度比较低。)
代码示例:
package com.kangfuqiang.util;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
/**
* <pre>
* Title:不重复的随机整数类
* Description: 用于依次获取 [MIN,MAX] 范围内的不重复随机整数;
* 使用说明:需要new一个该类的实例(传入min和max参数),然后 使用该实例 依次获得不重复的随机整数;
*
* ps:1M 的整数范围时,该实例占用的相关内存约为 4M 。
*
* </pre>
*/
public class NoRepeatRandomInt {
private static Logger log = LoggerFactory.getLogger(NoRepeatRandomInt.class);
/** 最小值(包含) */
public final int MIN;
/** 最大值(包含) */
public final int MAX;
/** 计数器,记录已经领取不重复的随机整数的次数 */
private int counter = 0;
/** 保存 [MIN,MAX] 范围内的所有整数*/
private int[] numArr ;
/**
* @param min
* @param max
* @exception IllegalArgumentException 如果 min > max,则抛出该异常
*/
public NoRepeatRandomInt(int min, int max) {
if(min>max){
String str = String.format("构造器参数错误,最小值不能大于最大值!min:%s,max:%s", min, max);
log.error(str);
throw new IllegalArgumentException( str );
}
this.MIN = min;
this.MAX = max;
numArr = new int[this.getOriginalCnt()];
for(int i=0; i<numArr.length; i++){
numArr[i] = i + this.MIN;
}
}
/**
* 领取 下一个不重复的随机整数
* @return
* @exception RuntimeException 如果 领取次数 超过 总个数范围,将抛出运行时异常
*/
public int next(){
if(this.getRemainCnt()<=0){
String str = String.format("领取次数 超过 总个数范围(%d个)!", this.getOriginalCnt());
log.error(str);
throw new RuntimeException(str);
}
int idx = (int)(Math.random() * this.getRemainCnt());
int ret = numArr[idx];
numArr[idx] = numArr[this.getRemainCnt()-1];
numArr[this.getRemainCnt()-1] = ret;
this.counter++;
return ret;
}
/** 获得原始个数 */
private int getOriginalCnt(){
return this.MAX - this.MIN + 1;
}
/** 获得剩余个数 */
private int getRemainCnt(){
return this.MAX - this.MIN + 1 - counter;
}
}
算法三:
使用Set集合来保证或保存不重复的随机整数。 这种算法适合 (返回数目/
范围数目)的值非常小 的情况,
其他情况还是使用上面的两种算法比较好。
PS:
网上还有一些其他的算法,但是大多时间复杂度比较高,空间复杂度也没有明显的好处。
1、遍历 已返回的随机数 的集合,以保证不重复随机整数。
2、初始化List后,随机排序一下(shuffle),然后依次返回。
3、初始化数组后,数组随机调换位置,然后依次返回。
欢迎大家交流、指点、评论与回复
分享到:
相关推荐
周咏基 -《论随机化算法的原理与设计》 ## 2000 陈 彧 《信息学竞赛中的思维方法》 方 奇 《动态规划》 高寒蕊 -《递推关系的建立及在信息学竞赛中的应用》 郭 一 -《数学模型及其在信息学竞赛中的应用》 ...
在这样的环境中,大量的重复数据同时进入中间件,特别是一个顾客长时间呆在同一个地方就会产生大量的重复数据,为了准确的去除冗余数据,我们需要在内存中长时间保存包括重复数据在内的所有RFID数据。当相对于RFID...
• 产生50~100 的随机整数 • 利用随机函数仅生成数字和字母 • 利用随机函数实现考试座位随机编排 • 日计帐中的余额累计 • 计扣个人所得税 • 统计月末考试中大于等于平均分的总分 • 利用CHAR 函数生成A~Z ...
2、修正“进制_十到十六”不支持长整数的BUG。 3、恢复3.75版的“时间_格林威治转北京”命令,设置参数可将13位时间戳转换成北京时间。 4、改善“类_通用对话框”打开与保存对话框拥有易全部属性,感谢易友【詠不言...
答:switch(expr1)中,expr1是一个整数表达式。因此传递给 switch 和 case 语句的参数应该是 int、 short、 char 或者 byte。long,string 都不能作用于swtich。 47.当一个线程进入一个对象的一个synchronized方法...
第一章:数据结构和算法 1.1 解压序列赋值给多个变量 1.2 解压可迭代对象赋值给多个变量 1.3 保留最后N个元素 1.4 查找最大或最小的N个元素 1.5 实现一个优先级队列 1.6 字典中的键映射多个值 1.7 字典排序 ...
3.1.2 随机方法 3.1.3 协议变异人工测试 3.1.4 变异或强制性测试 3.1.5 自动协议生成测试 3.2 模糊器类型 3.2.1 本地模糊器 3.2.2 远程模糊器 3.2.3 内存模糊器 3.2.4 模糊器框架 3.3 小结 第4章 数据表示和分析 4.1...
与开发人员在测试组环境多次重复以上步骤,发现11群的计次表话单有时正常,有时其出中继群号就为一个随机值,发生异常的频率比较高。为什么其它群的话单正常,唯独11群不正常呢?11群是四个群中最小的群,其中继计...
《C#开发实例大全(基础卷)》筛选、汇集了C#开发从基础知识到高级应用各个层面约600个实例及源代码,每个实例都按实例说明、关键技术、设计过程、详尽注释、秘笈心法的顺序进行了分析解读。全书分6篇共25章,主要...
关于数字签名:产生RSA密钥对(myKeyPair),得到RSA密钥对,产生Signature对象,对用私钥对信息(info)签名,用指定算法产生签名对象,用私钥初始化签名对象,将待签名的数据传送给签名对象(须在初始化之后),用公钥...
设计一个构造函数,当对象结束时,要释放整个二叉搜索树所占的内存空间(提示,通过后序遍历算法找到叶结点,并删除叶结点,不断重复此过程,直到整科树为空); 2、实现1所要求的代码后,运行设计好的代码,将...
关于数字签名:产生RSA密钥对(myKeyPair),得到RSA密钥对,产生Signature对象,对用私钥对信息(info)签名,用指定算法产生签名对象,用私钥初始化签名对象,将待签名的数据传送给签名对象(须在初始化之后),用公钥...
与cgi的区别在于servlet处于服务器进程中,它通过多线程方式运行其service方法,一个实例可以服务于多个请求,并且其实例一般不会销毁,而CGI对每个请求都产生新的进程,服务完成后就销毁,所以效率上低于servlet。...
与cgi的区别在于servlet处于服务器进程中,它通过多线程方式运行其service方法,一个实例可以服务于多个请求,并且其实例一般不会销毁,而CGI对每个请求都产生新的进程,服务完成后就销毁,所以效率上低于servlet。...
100 <br>0158 如何将二进制数转换为十六进制数 100 <br>0159 如何实现0~9之间随机整数 101 <br>0160 如何实现0~1之间随机数 101 <br>0161 如何返回数字的绝对值 101 <br>5.2 控件数据处理...