时间戳

首页 > 解决方案 > 如何在 C 中生成一个随机且唯一的整数数组？

c - 如何在 C 中生成一个随机且唯一的整数数组？

问题描述

我正在创建一个需要 17 个整数的数组的 C-prog，所有整数都小于 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() 继续生成一个数字，直到获得一个唯一的数字然后它是存储在数组中。如果数组中不存在这样的数字，则直接将其输入。

到目前为止，存储在数组中的数字并不是唯一的。

任何帮助，将不胜感激。

标签： carraysgcc

解决方案

这不是最佳解决方案，一旦解决了代码中的问题，您的时间复杂度为 O(n²)，您可以使用“Knuth Shuffle algorithm”将时间复杂度降低到 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;
}

推荐阅读