如果在数组中发现重复的数字，则用随机数字替换数组中的数字

Question

我试图生成一个指定大小的数组，用随机整数填充它，然后遍历数组以检查是否没有重复。测试时，我有一些不一致的地方。想知道是否可以使用嵌套的循环来完成，或者是否建议更好的方法？

class Program
{
    static void Main(string[] args)
    {
        int size = 10;
        int[] newArray = InitializeArrayWithNoDuplicates(size);
          for (int i = 0; i < newArray.Length; i++)
        {
          Console.WriteLine( newArray[i]);
        }

        Console.ReadKey(); 
    }

    static Random rng = new Random();

    public static int[] InitializeArrayWithNoDuplicates(int size)
    {
        int minValue = 1;
        int maxValue = 10; 
        int[] array = new int[size] ;

        for (int i = 0; i <array.Length; i++)
        {
           array[i] = rng.Next(minValue, maxValue);

              for (int j = i+1; j < array.Length-1; j++)
                    if (array[i] == array[j])
                     {
                    array[i] = rng.Next(minValue, maxValue);
                     }
           }return array;
    } 
}

Answer 1

Next（minValue，maxValue）中的第一个参数是一个包含的下限，而第二个参数是独占的下限，这意味着返回值应大于或等于minValue且小于maxValue。

https://msdn.microsoft.com/pl-pl/library/2dx6wyd4（v=vs.110）。aspx

因此

    int minValue = 1;
    int maxValue = 10; 

生成器只能返回九个不同的值，1到9，您无法用它们填充10项数组[]。

您必须假设更短的数组，或者允许随机值具有更大的跨度
或允许重复。。。

对于非常短的数据集，最快的方法是填充数组并生成数组的排列。假设你想把数字放在1。。N到N项数组中。首先准备阵列：

    int[] array = new int[N];

    for (int i = 0; i < N; ++i)
        array[i] = i+1;

这个打乱代码从i==N-1向下迭代到1，在每一步中它选择一个项目放在indexi：

    for (int i = N-1; i > 0; --i)
    {
        int j = rng.Next (0, i+1);
        swap (array[j], array[i]);    // exchange values
    }

请注意，在每次迭代中，我们从0到i取一个随机索引j，因此j==i可能意味着数组[i]的值保持不变。这样，在每次迭代中，我们从那些尚未绘制的数字中提取一个新的数字，并将其放置在连续的位置上，因此我们以相同的概率获得数组的每个可能排列（假设随机数生成器Next方法总是在其参数定义的区间内返回均匀分布的值）
当i达到0时，循环终止–索引0下没有项目，我们可以选择使用数组[0]进行交换。

如果数据的跨度比所需的数组长度稍长，但两个值都很小——比如说，100个值中需要80个值——那么可以创建一个数组来保留整个集合（即100个项），填充它，洗牌它，然后删除不需要的20个
如果你选择从数组的开始处放置物品，你也可以放弃洗牌的最后20步。

对于一组非常大的可能值，这是无效的。假设你需要一个随机序列，从一亿个值中选出500个值——你想分配、填充和洗牌100000000个项目数组，只得到500个值吗？当然不是
为了简单起见，假设您的数据空间也是一个整数区间，您可以构建一个整数的自平衡BST。最初，树是空的
然后重复这个步骤500次：生成一个随机数K并在树中查找；如果它不在那里，你添加它，它就会成为你的输出值之一。如果你找到了数字K，它是一个重复的，你重复这个步骤，从rng中再画一个K<重新选择相同数字的概率很低，在上一次迭代中是5亿到1亿，即1/200000。无论如何，这是可能发生的。

对于像自平衡BST这样的结构，对值的搜索可以限制为N的对数，因此对于N个输出值，您执行N次迭代，每次执行对数（N）步以检测可能的重复，因此整个时间复杂度约为N·对数（N）。

其他结构可以提供甚至更快的重复检测，从而导致更低的执行时间。

Answer 2

你的重复消除逻辑行不通。考虑数组开始的情况>代码> [ 1, 2，…] <代码>然后设置第三个元素。随机生成一个2。

然后开始内部循环。当j==1比较显示没有问题时。当j==2看到新值是一个dup，所以你重新滚动。但是你的重新滚动可能是1（第一个元素的dup，你不会再次检查）或2（第二个元素的dup，你不会再次检查）。

更一般地说，这种方法效率很低。对于这种特殊情况（将1到10中的所有10个数字按随机顺序排列），这样的方法可能更好：

• 创建可用值的列表L（每个数字1到10）
• 而L不是空的
  • 在1和L的大小之间生成随机数N
  • 将输出数组的下一个打开元素设置为L的第N个元素
  • 从L中删除第N个元素

  有很多方法可以实现这种方法。不要害怕维护适当数据结构的开销；与嵌套循环和随机/潜在无限次重试的算法相比，这算不上什么，而这正是您最初的方法的方向。