数组交集的实现如何工作？

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

考虑一个数组arr1 [] = {2，3，2，3，4，3}。

使用这种代码后，

map<int,int>mapp;

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

mapp将按照以下方式存储，

mapp [2] = 2

mapp [3] = 3

mapp [4] = 1

这意味着唯一元素在arr1中重复多少次。

现在回到主要部分。两个数组的交集表示两个数组中都具有的元素。

mapp[arr2[i]] >0 //4

此行确保arr2 [i]元素至少在arr1中存在一次。如果mapp [arr2 [i]] == 0，则表示它不在arr1中（混淆？）。为什么我要说arr1。因为我们通过arr1迭代了mapp。记住您评论为“ 3”的内容。

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

为您的5 ...

让我们看一个例子。

对于arr2中的每个元素，如果也位于arr1中，则将其划线。实际上，它将是交集后的数组元素。

arr1 = {2，2，2，2，3，5}

arr2 = {2，2，3，4}

在交点{2，2，3}之后

实际上是交叉的东西，

mapp[arr2[i]]--; //5

很难以这种方式演示。但是我尽力了：）

Answer 2

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：上一个示例包含重写

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

Answer 3

该算法正在使用std::map将数组中存储的每个值与找到的出现次数计数相关联。该地图已订购。

第一次迭代只计算第一个数组中存在的值。因此，如果第一个数组包含3、2、3和5，则语句std::map将更新地图以获取以下关联：

//3

第二次迭代遍历第二个数组。第一个数组中尚未存在的数字将被忽略（因为映射值最多为0，这是

key   counter value
2   ->   1
3   ->   2
5   ->   1

的目的。）

对于匹配的数字，它将减少地图中未匹配的值的数目并显示该值。

因此，如果第二个数组包含1、3、5、3、3，则迭代看起来如下

//4
该算法将按照第二个数组中数字出现的顺序打印结果。不幸的是，它为1 -> mapp[1] is 0 so this number is ignored (indeed it was not in the first array)
3 -> mapp[3] is 2 so the count is decreased to 1 and 3 is printed.  
5 -> MAPP[5] is 1 so the count is decreased to 0 and 5 is printed, 
3 -> mapp[3] is 1 (see above), so the cound is decreased to 0 and 3 is printed
3 -> mapp[3] is 0 (see above), so either 3 was never found in the first array, or all the count occurences were already matched.  So nothing is done.  
中所有尚未在mapp中的元素填充了arr2值，因为用arr1访问映射中的键的事实将为其创建0值。 。用[]检查映射中某个值的存在是更好的方法。