java - 用大小为O(n)的唯一随机数填充大小为n的Java中的数组

我必须编写代码，用范围0-10n内（包括）的唯一随机数填充大小为n的数组。我可以用O(n^2)复杂性来完成它，但是我需要用O(n)复杂性来完成它。我想不出一种方法，不需要生成随机数，然后返回部分填充的数组，检查数组中是否有重复项。
作为参考，这里是我的O(n^2)方法版本：

private static void fillWithUniqueN2(int[] numbers)
{
    Random rng = new Random();
    for (int i = 0; i < numbers.length; i++)
    {
        boolean added = false;
        while (!added)
        {
            int newNumber = rng.nextInt(numbers.length);
            boolean unique = true;

            for (int j = 0; j < i; j++)
            {
                if (newNumber == numbers[j])
                {
                    unique = false;
                }
            }

            if (unique)
            {
                numbers[i] = newNumber;
                added = true;
            }
        }
    }
}

最佳答案

在一个范围内生成唯一随机数的标准解决方案是：
生成范围-O（n）内所有数字的列表
洗牌列表-o（n）
从列表中提取前n个项-o（1）或o（n）
因此，整个操作将是O（n）。

关于java - 用大小为O(n)的唯一随机数填充大小为n的Java中的数组，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42494527/