指定范围内随机不重复数,高效算法?

1. 如果n不大,用一个长度为n的数组,取值之后将该元素删除(可以做到O(1),用交换法),重复m次。2. 同样的道理,数组元素是区间,每次删除一个区间,注意调整上下限。比如第一次产生0~100的随机数,去掉40~80区间后,第二次产生0~60的随机数,其中40~60对应80~100。
■网友
洗牌,摸牌。
■网友
第一个你就理解为是一副牌,有N张,现在从里面摸出m张来第二个你就理解为是m副牌,每副牌具体多少张看你题目的定义,比如m=4就是第一副10张,第二副20张,第三副40张,第四幅20张,然后从这m副牌里每副牌里取一张
■网友
要求“不重复”就不是“随机”了,所以方法取决于你对“随机”质量的要求。比如第一点,如果你只需要“看上去随机且不重复地”走过一个区间,随便选个质数p,并依次选择(p*i%N)位置上的值就行了。这是由于p,2p,3p…是任意N的同余类
■网友
如果范围不大,开个数组,random-shuffle,再在数组里面按次序取即可。随机打乱应该是每种语言都有实现了。


    推荐阅读