如何在C中生成随机唯一整数数组？

Question

我正在创建一个C-prog，它需要一个由17个整数组成的数组，所有整数都小于18并且是唯一的。这是我现在能做的：

int ques_arr[17];
int x,y;
time_t t;
srand((unsigned)time(&t));

for(int a=0; a<17; a++)
{
x=rand()%18; //Assume that srand() has been declared in the program
 for(int aa=0; aa<17; aa++)
 {
  if(x==ques_arr[aa])
   { do{
        y=0;
        y=rand()%18;
        }while(y==ques_arr[aa]);
      x=y; 
      ques_arr[a]=x;
    }else ques_arr[a]=x;
  }
}

我现在的算法是，每次rand（）生成一个数字时，都会在数组中检查这个数字是否已经存在，如果已经存在，则rand（）会继续生成一个数字，直到得到一个唯一的数字，然后将其存储在数组中，如果数组中不存在这样的数字，则直接输入到数组中。

Answer 1

这不是一个最佳解决方案，您的时间复杂度一旦您修复了您的代码中的问题是O(n²)，您可以使用“Knuth Shuffle算法”将时间复杂度降低到O(n)：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>

static int rrand(int value)
{
    return (int)((double)value * (rand() / (RAND_MAX + 1.0)));
}

static void randomize(int arr[], int size)
{
    for (int idx = 0; idx < size; idx++)
    {
        arr[idx] = idx;
    }
    for (int idx = size; idx > 1; idx--)
    {
        int num = rrand(idx);
        int tmp = arr[idx - 1];

        arr[idx - 1] = arr[num];
        arr[num] = tmp;
    }
}

int main(void)
{
    srand((unsigned)time(NULL));

    int arr[17] = {0};
    int size = sizeof arr / sizeof *arr;

    randomize(arr, size);
    for (int idx = 0; idx < size; idx++)
    {
        printf("%d\n", arr[idx]);
    }
    return 0;
}