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

Question

我必须编写代码，用 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;
            }   
        }       
    }
}

Answer 1

在一个范围内生成唯一随机数的标准解决方案是:

1. 生成范围内所有数字的列表 - O(n)

2. 打乱列表 - O(n)

3. 从列表中提取前 N 项 - O(1) 或 O(n)

因此整个操作将是 O(n)。