首页 > 代码库 > 如何更高效率的生成随机数组
如何更高效率的生成随机数组
现在我们有一个需求:生成长度为100的随机数组(数值范围0~99),数值无重复。
通常方法:
var _len = 100, _arrUsedFlag = [],_arrR=[]; for(var i=0;i<_len;i++){//初始化标志位数组,表示第N个数组是否已经被生成过 _arrUsedFlag.push(false); } i=0; for(;i<_len;i++){ var _isNewNum=false; //如果没有生成不重复的随机数,循环 while(_isNewNum==false){ var _newNum=Math.floor(Math.random()*100); //如果生成了新的无重复的随机数 if(!_arrUsedFlag[_newNum]){ _arrR.push(_newNum); _arrUsedFlag[_newNum]=true; _isNewNum=true; } } }
在上面的例子中,我们需要一个数组来标记某个数是否已经被生成。在循环中,我们需要判断是否某个随机数已经生成过,如果已经生成,那么我们就再生成一次。
假设有一个大小为N的随机序列,那么按照上面的算法,生成第一个随机数的期望为1,第二个随机数的期望为N/(N-1),第三个随机数的期望为N/(N-2),以此类推。这样子的效率很低。
下面我们来看另一种方法:
1 var _len = 100, _arrR = []; 2 for (var i = 0; i < _len; i++) { 3 _arrR.push(i); 4 } 5 i = 0; 6 for (; i < _len; i++) { 7 //每次 8 var _r = Math.floor(Math.random() * (_len - i)); 9 var _temp = _arrR[_r]; 10 _arrR[_r] = _arrR[_len - 1 - i]; 11 _arrR[_len - 1 - i] = _temp; 12 }
在上面的方法里,我们其实要做的就是对0~N-1(N=100)排序的数组进行重新排列。
第一次在N个数中随机一个值,将其存放在数组的最后一位。
第二次在N-1个数中随机一个值,将其存放在数组的倒数第二位。
第k次在N-k个数中随机一个值,将其存放在数组的N-k位。
第二种算法无论在时间和空间复杂度方面都比第一种要低许多.
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。