c++ - 创建 5 个 1 到 20 之间唯一整数的数组的算法

Question

这个问题已经有答案了:

Unique (non-repeating) random numbers in O(1)? (22 个回答)

已关闭 2 年前。

我的目标是创建一个由 5 个 1 到 20 之间的唯一整数组成的数组。是否有比我下面使用的算法更好的算法？

它有效，我认为它具有恒定的时间复杂度，因为循环不依赖于变量输入，但我想找出是否有更有效、更干净或更简单的方法来编写它。

int * getRandom( ) {

  static int choices[5] = {};
  srand((unsigned)time(NULL));
   
  for (int i = 0; i < 5; i++) {

    int generated = 1 + rand() % 20;
    for (int j = 0; j < 5; j++){
      if(choices[j] == generated){
        i--;
      }
    }
    
    choices[i] = generated;
    cout << choices[i] << endl;
  }

  return choices;
}

非常感谢您的任何反馈。我是算法新手。

Answer 1

我能想到的最简单的方法就是创建所有 20 个数字的数组，其中 choices[i] = i+1 ，用 std::random_shuffle 将它们洗牌并取 5 个第一个元素。可能会慢一些，但很难引入错误，并且考虑到较小的固定大小 - 可能没问题。

顺便说一句，您的版本有一个错误。您执行行 choices[i] = generated;即使您找到生成的 - 这可能会创建 generated 的拷贝值(value)。假设 i = 3，生成的值等于 j = 0 处的元素，现在您递减 i 并分配 choices[2] - 等于 choices[0] .