创建由 5 个介于 1 和 20 之间的唯一整数组成的数组的算法

Question

我的目标是创建一个由 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

生成1到16的5个随机数，允许重复
排序
第2个加1，第3个加2，第4个加3，第5个加4。

最后一步通过将具有重复项的可能序列重新映射为具有唯一整数的序列，将范围从 [1,16] 转换为 [1,20]。例如，[1,2,10,10,16] 变为 [1,3,12,13,20]。转换完全是双射的，因此您永远不需要丢弃和重新采样。

Answer 2

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

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

Answer 3

C++17 代码，解释原因和内容。如果您还有任何问题，请随时提出，我很乐意为您提供帮助

#include <iostream>
#include <array>
#include <string>
#include <random>
#include <type_traits>

// container for random numbers.
// by putting the random numbers + generator inside a class
// we get better control over the lifecycle.
// e.g. what gets called when.
// Now we know the generation gets called at constructor time.
class integer_random_numbers
{
public:
    // use std::size_t for things used in loops and must be >= 0
    integer_random_numbers(std::size_t number, int minimum, int maximum)
    {
        // initialize the random generator to be trully random
        // look at documentation for <random>, it is the C++ way for random numbers
        std::mt19937 generator(std::random_device{}());

        // make sure all numbers have an equal chance. range is inclusive 
        std::uniform_int_distribution<int> distribution(minimum, maximum);

        // m_values is a std::vector, which is an array of which
        // the length be resized at runtime.  
        for (auto n = 0; n < number; ++n)
        {
            int new_random_value{};

            // generate unique number
            do
            {
                new_random_value = distribution(generator);
            } while (std::find(m_values.begin(), m_values.end(), new_random_value) != m_values.end());
        
            m_values.push_back(new_random_value);
        }
    }

    // give the class an array index operator
    // so we can use it as an array later
    int& operator[](const std::size_t index)
    {
        // use bounds checking from std::vector
        return m_values.at(index);
    }

    // reutnr the number of numbers we generated
    std::size_t size() const noexcept
    {
        return m_values.size();
    }

private:
    // use a vector, since we specify the size at runtime.
    std::vector<int> m_values;
};

// Create a static instance of the class, this will
// run the constructor only once (at start of program)
static integer_random_numbers my_random_numbers{ 5, 1, 20 };

int main()
{
    // And now we can use my_random_numbers as an array
    for (auto n = 0; n < my_random_numbers.size(); ++n)
    {
        std::cout << my_random_numbers[n] << std::endl;
    }
}

创建由 5 个介于 1 和 20 之间的唯一整数组成的数组的算法

Algorithm for creating an array of 5 unique integers between 1 and 20

c++

performance

random

array-algorithms