使用不规则数组的线性搜索？

Question

我有一个程序，通过数组创建了100个随机元素。这100个随机值是唯一的，并且每个值只显示一次。

虽然使用线性搜索，但它仍在查找整个数组。我该如何将 Jagged Array 添加到其中，以便仅“扫描”剩余的位置？（假设我保持表格最多100个元素，因此如果生成一个随机值，则数组保持99个元素，其中线性搜索扫描并...）

我认为我需要在FoundLinearInArray中实现嵌套数组？

希望这有任何意义。谢谢。

 private int ValidNumber(int[] T, int X, int Range)
    {
        Random RndInt = new Random();
        do
        {
            X = RndInt.Next(1, Range + 1);
        } while (FoundLinearInArray(T, X));

        return X; 

    }/*ValidNumber*/

    private bool FoundLinearInArray(int[] A, int X)
    {
        byte I = 0;
        while ((I < A.Length) && (A[I] != X))
        {
            I++;
        }
        return (I < A.Length);
    }/*FoundInArray*/


    public void FillArray(int[] T, int Range)
    {
        for (byte I = 0; I < T.Length; I++)
        {
            T[I] = ValidNumber(T, I, Range);
        }

    }/*FillArray*/

- Nerathas

---

读这个的时候我不得不在脑海中反复默念“T不是类型参数”！ :) - Paul Ruane

我觉得我可能需要一些澄清。你是说你有一个预先填充了100个值的数组，你的程序需要生成一个不在这100个值集合中的新值吗？还是你想用100个唯一的值填充一个空的（零初始化）数组？ - Paul Ruane

不，我的问题并不完全是关于生成数字本身的！我在想是否可以使用锯齿数组来实现，因为线性搜索一直遍历整个数组？ - Nerathas

Answer 1

看起来你想填充数组，并确保其中的每个项都是唯一的？如果是这样，请将生成的每个数字放入Hashset中。对Hashset的查找是O(1)（或者可能是对数级别）--您可以将一百万个项目放入其中，仍然具有极高的性能查找。

- JMarsch

Answer 2

我不确定这是否是您要寻找的内容，但这里有一段代码片段，用于在范围内填充一组唯一随机数的数组。正如JMarsch建议的那样，它使用HashSet来跟踪已使用的数字。

它还快速检查以确保问题可解 - 如果范围小于数组大小，则没有足够的唯一数字来填充数组。

最后，它只创建一次随机数生成器，而不是多次，这可以更好地分配数字。由于数字必须是唯一的，在这种情况下，您永远不会注意到，但我认为这是一个好习惯。

    private int GenerateUniqueRandomNumber(Random chaos, HashSet<int> used, int range)
    {
        while (true)
        {
            int candidate = chaos.Next(range);
            if (!used.Contains(candidate))
            {
                used.Add(candidate);
                return candidate;
            }
        }
    }



    public void FillArray(int[] array, int range)
    {
        if (range < array.Length)
        {
            throw new ArgumentException("Range is too small");
        }

        Random chaos = new Random();
        HashSet<int> used = new HashSet<int>();

        for (int i = 0; i < array.Length; i++)
        {
            array[i] = GenerateUniqueRandomNumber(chaos, used, range);
        }
    }

希望这能有所帮助。

- Doug

Answer 3

static int[] FillArray(int low, int high, int count)
    {
        Random rand = new Random();
        HashSet<int> Data = new HashSet<int>();
        while (Data.Count() < count)
            Data.Add(rand.Next(low, high));
        return Data.ToArray();
    }

这与JMarsch的建议类似。 哈希集是正确的选择。

- tbischel