※ 引述《qeagle (神啊请让我失恋吧)》之铭言： : 请问这题要怎麽着手 : 我想产生一些乱数序列以供测试排序功能用 : 产生乱数简单,但要保持其乱数产生顺序,又不能有重覆.. : 不知道大家会怎麽写好,先产生1000个,再一个个检查有无重覆吗... 关於这个问题, 没有完美的通解, 要看你的乱数值的范围, 与你要产生的乱数个数来决定 1.假如你的值的范围不大, 比如说扑克牌洗牌, 或从 0~几十万的数值范围(m)里取(n)个 不重复的乱数值, 最有效率的方法是阵列取值法, 虚拟码如下 for(i in 0..m-1) e[i]=i; for(i in n-1..0) { r=乱数 0..i out(e[r]); e[r]=e[i]; } 它需要O(m)的储存空间与O(n)的执行时间. 但因回圈内每次的乱数范围会变, 有些乱数产生器可能会有输出不均匀问题. 假如你有足够的记忆体空间, 且上面问题可以解决, 它是一个很好的选择. 2.但假如你的值的范围很大. 比如说要从 0~2^64 里面选出1万个不重复的数字, 方法1 就 有执行上的困难, 因为你难以找出那麽大的储存空间 ( 记忆体 ), 那先取值然後检查是 否已出现过就是比较可行的方案了, 虚拟码如下 set<int64> oUsed; for(int i=0;i<10000;i++) { int64 r= 某乱数函数 if (!oUsed.insert(r).second) continue; out(r); } 当然用 hashset 通常会更快, 这里只讨论方法. 当然实际情况下, 问题可能介於两者之间, 选择就要评经验与智慧了. -- Do not depend on others without effort... 当我年轻时,请教别人问题时常听到上面那句话. 当时心里偶而会有些小小抱怨. 当时间过去,我偶而会想到上面那句话, 心中十分感谢当初告诉我那句话的人. 当发现问题时,最有价值的不是问题的答案, 而是找到解决的方向,并在努力的过程里具备解决问题的能力. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 211.74.232.254