用随机数填充数组

Question

我试图用随机序列中1-20的数字填充20个整数的数组.这是我的代码:

 int lookup[20]={0}; 
 int array[20]={0};
 srand(time(NULL));
 for(int i=0;i<20;++i){ 
    bool done=false;
    while(!done){
      int n=rand()%20;
      if(lookup[n]==0){
          array[i]=n;
          lookup[n]=1;
          done=true;
      }
    }
 }

我创建了一个查找数组来检查是否还没有选择随机数并将其存储在数组中.正如你所看到的,我创建了2个循环,一个用于遍历数组,而while用于选择随机数.在每次循环迭代中,数字可能会重新出现并导致另一个while循环.有没有更快的方法来做到这一点？

Answer 1

你可以按顺序填充数组,然后将其洗牌.这样可以防止不得不进行超过20次随机数生成.

Fisher-Yates shuffle:可以在O(n)时间完成.

来自维基百科:

正确实施,Fisher-Yates shuffle是公正的,因此每个排列都是同样可能的.该算法的现代版本也相当有效,只需要与被洗牌的项目数量成比例的时间,而不需要额外的存储空间.

Answer 2

看看std::random_shuffle和std::vector.

Answer 3

您可以使用1到20之间的数字填充数组并使用std :: random_shuffle

请注意,简单的数组将不需要矢量.
例如:

#include <iostream>
#include <algorithm>

using namespace std;

int main( void )
{
        int array[] = { 0, 1, 2, 3, 4 };

        srand( unsigned( time(NULL) ) );

        random_shuffle(array, array+5);

        for(int i=0; i<5; i++)
                cout << array[i] << endl;

        return 0;
}