c# - C# 中的随机数生成器 - 唯一值

Question

我正忙于使用 C# 编写数组代码。我可以用随机生成器填充它，但现在我的问题是我该怎么做，这样我就可以检查该值是否已经在数组中，如果是，则生成一个新值

额外信息:
最大值:100
元素数量:100

重要 PLZ 进一步研究我的想法

我的想法

public void FillArray(int[] A, int Range)
{
    for (int I = 0; I < A.Length; I++)
    {
        A[I] = ValidNumber(T, I, Range);
    }
} /* Fill Array */

选择排序的实现

public void SelectionSort(int[] A)
{
    int K, X;
    for (int I = 0; I < A.Length - 1; I++)
    {
        K = I;
        X = A[K];
        for (int J = I + 1; J < A.Length; J++)
        {
            if (A[J] < X)
            {
                K = J;
                X = A[K];
            }
        }
        A[K] = A[I];
        A[I] = X;
    }
} /* Selection sort */

这些只是一些想法，现在我想知道如何修复它，所以我可以使用选择排序查看是否有 allread (fillarray)，如果是这样的话，用一个新的随机值替换它。所以我想用整数创建一个随机数组 - 从 1 到 100 随机排列

Answer 1

how do i do this but so that i can check if the value is already in the array and if so generate an new value

永远不要那样做，因为这是一个非常糟糕的主意。

为了说明为什么这是一个糟糕的想法，请考虑同一问题的另一个版本:通过以下过程将一百万个数字按随机顺序排序:

1. 从一到一百万中选择一个数字。
2. 检查它是否已经在列表中。
3. 如果是，返回第一步
4. 否则，将号码添加到列表中。
5. 列表中有 100 万个项目吗？如果是，你就完成了。如果不是，请返回步骤 1。

显然这有效。这是个好主意吗？假设你快完成了。 list 上有 999999 项。唯一缺少的项目是 857313。你是做什么的？您选择一个随机数，例如 12。现在您检查列表中的 999999 个项目，看看是否有任何一个是 12。12 可能是您选择的第一个数字之一，因此找到它可能很快。或者它可能是最后一个，所以需要很长时间。平均需要 500000 次检查才能确定 12 个是否在列表中。确实如此，因为列表中只缺少一个数字。

12 没有成功。回到开头。选择另一个随机数，例如 53259。它在列表中吗？另一个 50 万支票。

继续这样做，直到生成 857313，这种情况每百万次尝试就会发生一次。

因此，平均而言，将最后一项放入列表需要 500000 x 1000000 = 5000 亿次比较。可能需要更多时间。可能需要数万亿次比较。或者你可能会很幸运，需要一个。但平均而言，有五万亿次比较。

这是一种生成随机排序列表的糟糕方式。

有两种对列表进行随机排序的好方法。

(1) 制作一个可以给定排序函数对列表进行排序的设备。提供基于随机种子的稳定排序。

请注意，当被问及“A 是否大于 B？”时，您应该不通过创建一个返回随机结果的方法来产生随机排序。那是一个不稳定的排序；许多排序算法都基于稳定的排序顺序，并且在给定不稳定的排序顺序时会进入无限循环或出现其他不良行为。

这个算法是 O(n lg n) 并且有一个很好的特性，那就是很容易用标准零件写出来，正如其他答案所表明的那样。对于典型实现中的小型列表，它也非常快。

(2) 按索引从源列表中随机选择一个项目，将其从源列表中删除，然后将其放入目标列表。

后者称为 Knuth Shuffle 或 Fischer-Yates Shuffle，是一种非常快的算法。您可以“就地”执行此操作，将现有数组更改为打乱顺序，或者创建一个新列表。它还具有一个不错的属性，您可以“付费玩”，根据需要洗牌列表的“顶部”。如果您有一百万个项目需要洗牌，但您只需要前一百个，那么您只需计算出前一百个的排序顺序即可。