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

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 将如下存储，

映射[2] = 2

映射[3] = 3

映射[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

该算法使用 std::map 将数组中存储的每个值与找到的出现次数相关联。地图是有序的。

第一次迭代只计算第一个数组中存在的值。因此，如果第一个数组包含 3、2、3 和 5，语句 //3 将更新映射以获得以下关联：

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

第二次迭代遍历第二个数组。不在第一个数组中的数字将被忽略（因为映射值最多为 0，这就是 //4 的目的）。

对于匹配个数，减少地图中不匹配值的个数，并显示该值。

因此，如果第二个数组包含 1、3、5、3、3，则迭代将如下所示

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.

该算法将按照第二个数组中数字出现的顺序打印结果。不幸的是，它为 arr2 中尚未存在于 arr1 中的所有元素填充了 0 值 mapp，因为使用 [=18= 访问映射中的键的绝对事实] 将为它创建一个 0 值。使用 .find() 检查地图中是否存在值是更好的方法。

Answer 3

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：前面的例子包含rewrite

因此，当密钥出现在 arr1 以及 arr2 中时，我们只输入 if。如果是这种情况，我们只需将计数器减 1，这样每次值在两个数组中时它只显示一次。

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

How does this implementation of array intersection work?

c++

arrays

algorithm

stl

intersection