c++ - 这个数组交集的实现是如何工作的？

Question

此代码查找两个未排序数组的交集。

void intersection(int arr1[],int m,int arr2[],int n)    //where m=size of arr1 and n=size of arr2
{
  map<int,int>mapp;

  for(int i=0;i<m;i++)
     mapp[arr1[i]]++;    //3

  for(int i=0;i<n;i++)
  {
    if(mapp[arr2[i]] >0)    //4
    {
      mapp[arr2[i]]--;     //5
      cout<<arr2[i] <<endl;
    } 
  }
}

第 3、4 和 5 行实际上要做什么？

Answer 1

3:可以这样写的更清楚一点:

for (int i = 0; i < m; i++) {
    int value1 = arr1[i];
    int currentCount = mapp[value1];
    mapp[value1] = currentCount + 1;
}

这使得它易于解释。将 arr1 的所有值作为键存储在 mapp 中，并在每次遇到相同值时将其值递增 1。这里我们假设任何值都应始终从 0 开始。

4:同样，我们将重写它以使其变得更加清晰:

for (int i = 0; i < n; i++) {
    int value2 = arr2[i];
    int currentCount = mapp[value2];
    if (currentCount > 0) {
        mapp[value2] = currentCount - 1;
        cout << value2 << endl;
    }
}

在 if 语句中，我们试图找到一个已经存在于 mapp 中的值。再次假设值默认为 0:我们将跳过第一个数组中未找到的任何值。如果找到，它的计数将大于 0，我们在 if 中继续。

5:前面的例子包含重写

所以我们只在 arr1 和 arr2 中存在 key 时才输入 if。如果是这种情况，我们只需将计数器减 1，这样每次两个数组中的值都只显示一次。