如何尽可能有效地比较两个不同长度的数组

Question

我试图比较第一个数组的值，看看它是否存在于另一个数组中。我有两个for循环，它适用于较小的数组大小，但当我增加长度时，编译需要很长时间。

bool value_check(int arr1[], int arr2[], int nums)
{
int  value = 0;
for(int i = 0; i < nums; i++)
{
value = arr1[i];
for(int j = 0; j < nums; j++)
{
if (value == arr2[j])
{
return true;
}
}
}
return false;
}

Answer 1

如何尽可能有效地比较不同长度的两个数组？

通常要做的事情是对数组进行排序。一旦完成，比较就很快了，因为您可以一起遍历这两个数组。

对数组进行排序可以在O(n-log(n((时间内完成，之后对它们进行比较只需要O(n(时间，因此总体而言，您会得到O(n-logn((的复杂性。

Answer 2

正如Caleb所指出的，首先对输入进行排序是渐进更快的。

这里有一些使用std::set_intersection的东西，并且仍然能够急切地返回。

struct Found{};
struct Finder : std::iterator<std::output_iterator_tag, void, void, void, void> // for brevity
{
Finder* operator->() { return this; }
Finder& operator*() { return *this; }
Finder& operator=(int) { throw Found{}; }
Finder& operator++() { return *this; }
Finder& operator++(int) { return *this; }
};
bool any_intersection(std::vector<int> lhs, std::vector<int> rhs)
{    
std::sort(lhs.begin(), lhs.end());
std::sort(rhs.begin(), rhs.end());
try { std::set_intersection(lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), Finder{}); }
catch (Found &) { return true; }
return false;
}

Answer 3

如果您不介意使用stl，那么无序映射可能会更高效。

将第一个数组插入无序映射中，然后遍历第二个数组并查找表以找到匹配项。第一场比赛返回。

这可以在O(n(中完成

bool value_check(int arr1[], int arr2[], int nums)
{
std::unordered_map<int, int> first;
for (int i = 0; i < nums; i++)
{
if (!first.count(arr1[i]))
first[arr1[i]] = 1;
else
first[arr1[i]]++;
}
for (int i = 0; i < nums; i++)
{
if (first.count(arr2[i]) > 0)
{ 
return true;
}
}
return false;
}