c++ - 数组交集的此实现如何工作？

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

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行中试图做什么？

最佳答案

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 -statement中，我们尝试找到mapp中已经存在的值。
再次假设值默认为0:我们将跳过第一个数组中未找到的任何值。
如果找到它，它的计数将大于0，我们继续在if内部。

5 :上一个示例包含重写

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