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

Question

我在使用编码的教程时遇到了问题.

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

问题是,教程有这个要求:

该解决方案在合理的时间内工作,有100万件物品

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

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

Answer 1

在任意数组中查找数字将不可避免地占用O(N)(线性到输入)时间(因为您无法对任何给定索引上的内容做出任何假设,因此您必须在最坏的情况下访问它们).

阵列排序时情况会有所改善 - 在这种情况下,您可以使用二进制搜索来及时查找值O(log n).这是内置的.NET using Array.BinarySearch方法.如果您只需要搜索一次该值,这是最佳解决方案.

if ( Array.BinarySearch(data, number) >= 0 )
{
   //found
}

最后,您将多次搜索数组,更好的选择是首先HashSet<int>从数组中创建一个.在这种情况下,任何后续查询将以平均O(1)时间(常量)返回.在这种情况下,你需要记住,创建HashSet<int>遗嘱本身需要O(n)时间和内存.如果要求您多次搜索该值,则此解决方案仅值得使用.如果你只搜索一次,那么你最好只需要一次进入阵列O(N),你也可以节省内存.

var lookup = new HashSet<int>(data);
if ( lookup.Contains(number) )
{
   //do something
}