首页 > C++,在1-n的范围内生成m个不同的随机数

C++,在1-n的范围内生成m个不同的随机数

不知道怎么搜英文的解决。只好来这边问了

C++里面,想实现比如:

范围给定为1-25,然后要求生成5个随机数,那么可能的结果是:1,2,8,4,5,而不会是:5,4,3,5,5(出现多个同一数字)。


csdn上的一种算法


将 n 个数洗牌后,取前 m 个。
可以参考 Fisher-Yates 。

优化:用 Fisher-Yates 算法决定前 m 个数即可。


通用的有两种方法:
1.重复再随机
这种方法是在[L,R]中先随机一个数,如果这个数之前取过,那么重复这个过程,直到取到不同的数为止。
不过这种方法在n个数取m个随机(m接近于n)时,时间复杂度将会很大。
这种方法的时间复杂度最坏为O(无穷),但是空间复杂度很小为O(1)。
2.队列法
首先我们出师一个[L,R]的一维数组,然后在[L,R]中随机一个下标作为新产生的随机数,然后将该随机数与下标为R的元素交换,然后再在[L,R-1]中随机新的随机数……以此递归,就可以在短时间内取到想要的随机数列。
这种方法的时间复杂度为O(m),但是空间复杂度会达到O(n)。


使用 shuffle(C++11、C++14)或 random_shuffle(C++98)来让包含 1 到 n 的数组随机排序,取前 m 个即可。

http://en.cppreference.com/w/cpp/algorithm/random_shuffle

下面的代码需要支持 C++11 的编译器才能编译。

#include <random>
#include <algorithm>
#include <iterator>
#include <iostream>

int main() {
    // assume m is 5 and n is 25.
    int m = 5;
    int n = 25;

    // initialize numbers.
    std::vector<int> v(n);
    std::iota(v.begin(), v.end(), 1);

    // do random shuffle.
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(v.begin(), v.end(), g);

    // show first m numbers.
    std::copy_n(v.begin(), m, std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;

    return 0;
}

我C++基本不会,不过我有两个思路:

  1. 取到一个随机数之后就记录下来(比如java中可以用hashmap来记录),然后下次去随机数的时候,如果已经被取了,就重新取,直至成功。不过这个方法不好的地方在于如果要取的随机数数量比较大,效率较低。

  2. 一个int数组1-25(数组下标范围),取随机数,如果随机数不是最后一个数,将取到的数移到数组最后一位,然后第二次取1-24(数组下标范围),取到的移到最后一位,。。。。。依次迭代下去即可。


直接random_shuffle就可以,
如果n特别大,可以直接随机,然后如果重复就重新随机。


srand((unsigned)time(NULL));
rand()%n
【热门文章】
【热门文章】