快速检查一个非常大的数组中是否存在数字（C#）

Question

玩编码游戏教程时遇到问题。

目标是检查数组int中是否存在。int

问题是，教程有这个要求：

该解决方案在合理的时间内适用于一百万个项目

我尝试了许多不同的方法，如 LINQ、Dictionary二进制搜索、指数搜索和其他一些方法，但仍然失败。

谁能告诉我解决这个问题的最快方法？

Answer 1

在任意数组中查找一个数字将不可避免地花费O(N)（与输入呈线性关系）时间（因为您无法对任何给定索引上的内容做出任何假设，因此您只需要在最坏的情况下访问它们即可）。对数组进行排序后，情况会有所改善——在这种情况下，您可以使用二分搜索及时找到值O(log n)。这是内置的 .NET 使用Array.BinarySearch方法。如果您只需要搜索一次值，这是最好的解决方案。if ( Array.BinarySearch(data, number) >= 0 ){&nbsp; &nbsp;//found}最后，您将多次搜索数组，更好的选择是首先HashSet<int>从数组中创建一个。在这种情况下，任何后续查询都将以平均O(1)时间（常数）返回。但是，在这种情况下，您需要记住，创建HashSet<int>遗嘱本身需要O(n)时间和记忆。仅当系统要求您多次搜索该值时，此解决方案才值得使用。如果你只搜索一次，那么你最好只遍历一次数组，这样O(N)你也可以节省内存。var lookup = new HashSet<int>(data);if ( lookup.Contains(number) ){&nbsp; &nbsp;//do something}