快速向量元素比较

Question

我想比较用整数填充的向量的元素，以查看具有相同值（并对它们进行计数）的元素是否为 。

因此，例如，如果a[i]==x，有没有b[j]==x？

浮现在脑海的第一个实现，当然是最简单的一个：

for (int i=0; i < a.size(); i++) { 
    for (int j=0; j < b.size(); j++) { 
    if (a[i]==b[j]) {counter++;} 
    } 

这是这样的大载体放缓。 我曾经想过交替算法，但我对不熟练的实施 是正确的，所以在这里它是，我有又和我的问题：

for (int i = 0; i < n; i++) { 
    for (int j = 0; j < m; j++) { 
     if (b[j] >= a[i]) { 
     counter++; 
     for (int k = i + 1; k < n; k++) { 
      if (a[k] >= b[j+1]) { 
      counter++; 
      for (int l = k + 1; l < m; l++) { 
       if (b[l] >= a[k]) { 
       counter++; 
       .... 
       } 
      } 
      } 
     } 
     } 
    } 
    } 

流程是，我开始比较a的第一个元素与b的元素。当我点击时，我跳转到矢量b，并将其下一个元素与a的元素进行比较，该元素位于a元素之后，与之前进行比较。 （由于a和b的元素存储在升序，一旦b我正在与比较元件比的a元件更大的变更向量上> =不==）

这应该是很容易我想，这是一个自称功能的函数。 但我无法将头围住它。

我希望有人能够理解我想要做什么，但目前我无法更好地解释它。从理论上讲，我认为这对于向量的升序应该更快，因为您只需进行N次比较（N代表更大的向量的大小），而不是N*M。

Answer 1

这是合并两个排序向量的经典问题的变化。

如果向量进行排序，你需要做的全部是矢量b执行增量线性搜索矢量a的时序元件。 b中的每个搜索都是从先前的搜索停止的地方开始的。这种方法将需要O(a.size() + b.size())比较。

int count = 0; 

int j = 0; 
for (int i = 0; i < a.size(); ++i) 
    for (; j < b.size() && b[j] <= a[i]; ++j) 
    if (b[j] == a[i]) 
     ++count; 

如果你仔细观察，你会发现这是完全一样的算法，如@ Anedar的答案，从一个“不同的制高点”刚表示。

然而，如果这两个向量有显著不同长度的（比如说，a比b短得多），那么它可能是有意义采取的a时序元件和b做二进制搜索。同样，b中的每个搜索都可以从之前找到的b元素中“向右”运行。这种方法将需要O(a.size() * log b.size())比较。

如果a.size() ~ b.size()则O(a.size() + b.size())优于O(a.size() * log b.size())。但是如果a.size() << b.size()，那么它是相反的。

Answer 2

既然你说，元素的顺序存储，你可以做这样的事情：

int i=0; 
int j=0; 

while(i< a.size() && j<b.size()){ 
    if(a[i]==b[j]){ 
    ++counter; 
    ++i; 
    ++j; 
    }else if(a[i]<b[j]){ 
    ++i; 
    }else{ 
    ++j; 
    } 
} 

Answer 3

如果不需要使用该向量，则可以使用std :: multiset作为两个集合中值的容器。

这个std :: multiset容器允许插入重复的值，并在相同的时间值被排序。你可以用std :: multiset :: count获取元素的数量。

O（logN）复杂度将执行一次检查，以检查B中是否包含所有来自B的值，并且最坏情况下的复杂计数是M（logN）。 std :: map可以达到同样的效果，但是设置的内存比map更少，使用起来也更简单。

如果值是在集合B中不止一次只有一个检查可以在集合A进行