使用哈希查找不常见的元素

Question

我认为这是一个相当常见的问题，但我没有找到任何在 C++ 中使用散列的答案。

我有两个数组，长度相同，包含一些元素，例如：

A={5,3,5,4,2}
B={3,4,1,2,1}

这里，不常见的元素是：{5,5,1,1}

我尝试过这种方法——在排序后对两个数组迭代一个 while 循环:

while(i<n && j<n) {
    if(a[i]<b[j])
            uncommon[k++]=a[i++];
    else if (a[i] > b[j])
            uncommon[k++]=b[j++];
    else {    
            i++;
            j++;
    }
}
while(i<n && a[i]!=b[j-1])
    uncommon[k++]=a[i++];
while(j < n && b[j]!=a[i-1])
    uncommon[k++]=b[j++];

我得到了正确的答案。但是，我想要一种在时间复杂度方面更好的方法，因为每次对两个数组进行排序可能在计算上很昂贵。

我尝试进行哈希运算，但无法完全弄清楚。

从arr1[]插入元素:

set<int> uncommon; 
    for (int i=0;i<n1;i++) 
        uncommon.insert(arr1[i]);

比较arr2[]个元素：

    for (int i = 0; i < n2; i++) 
        if (uncommon.find(arr2[i]) != uncommon.end())

现在，我无法做的是只将那些对它们都不常见的元素发送到不常见的数组[]。

谢谢！

Answer 1

首先，您需要找到一种方法来区分同一数组中包含的相同值（例如，第一个数组中的 5 和 5，第二个数组中的 1 和 1）。这是降低整体复杂度的关键，否则你做不到O(nlogn)。这个任务的一个很好的可能算法是创建一个包装对象来保存你的实际值，并在你的数组中放入指向那些具有实际数据的包装对象的指针，这样你的指针地址将作为对象的唯一标识符。这种包装将花费您 O(n1+n2) 次操作，但还会额外花费 O(n1+n2) space.

现在你的问题是你在两个数组中只有每个数组唯一的元素，你想找到不常见的元素。这意味着 (Union of both array elements) - (Intersection of both array elements)。因此，您需要做的就是将第一个数组的所有元素推入一个散列映射（复杂度O(n1)），然后开始将第二个数组的所有元素推入同一个散列映射（复杂度O(n1)） O(n2))，通过检测冲突（第一个数组中的元素与第二个数组中的元素相等）。在最坏的情况下，此比较步骤将需要 O(n2) 次比较。因此，为了获得最大的性能优化，您可以在开始将元素推入哈希映射之前检查数组的大小，并交换数组，以便第一次推入最长的数组。您的总体算法复杂度为 O(n1+n2) 推送（散列）和 O(n2) 比较。

实施是最无聊的事情，所以我把它交给你;)

Answer 2

首先，std::set与散列没有任何关系。集合和映射是有序的容器。实现可能不同，但很可能是二叉搜索树。无论你做什么，你都不会比 nlogn 更快 - 与排序相同的复杂性。如果您对 nlogn 和排序没问题，我强烈建议只使用 set_symmetric_difference 算法 https://en.cppreference.com/w/cpp/algorithm/set_symmetric_difference ，它需要两个排序的容器。

但是如果你坚持依赖散列的实现，你应该使用std::unordered_set或std::unordered_map。这样你可以比 nlogn 更快。您可以在 nm 时间内得到答案，其中 n = a.size() 和 m = b.size()。您应该创建两个 unordered_set`s：hashed_a、hashed_b 并在两个循环中检查 hashed_a 中的哪些元素不在 hashed_b 中，以及 hashed_b 中的哪些元素=32=] 不在 hashed_a 中。这是一个伪代码：

create hashed_a and hashed_b
create set_result // for the result
for (a_v : hashed_a) 
  if (a_v not in hashed_b)
    set_result.insert(a_v)
for (b_v : hashed_b) 
  if (b_v not in hashed_a)
    set_result.insert(b_v)
return set_result // it holds the symmetric diference, which you need

更新： 如评论中所述，我的回答不算重复。为重复项修改它的最简单方法是将 unordered_map 与集合中元素的键和遇到次数的值一起使用。

Answer 3

一个没有排序的解决方案（也没有散列，但你似乎更关心复杂性而不是散列本身）是要注意以下几点：不常见的元素 e 是恰好在一个多重集中的元素。

这意味着所有不常见元素的多重集是 2 个多重集之间的并集：

S1 = A 中不在 B 中的元素
S2 = B 中不在 A 中的元素

使用 std::set_difference，你得到：

#include <set>
#include <vector>
#include <iostream>
#include <algorithm>
int main() {
    std::multiset<int> ms1{5,3,5,4,2};


    std::multiset<int> ms2{3,4,1,2,1};

    std::vector<int> v;
    std::set_difference( ms1.begin(), ms1.end(), ms2.begin(), ms2.end(), std::back_inserter(v));
    std::set_difference( ms2.begin(), ms2.end(), ms1.begin(), ms1.end(), std::back_inserter(v));

    for(int e : v)
        std::cout << e << ' ';
    
    return 0;
}

输出：

5 5 1 1

此代码的复杂度为 4。(N1+N2 -1) 其中 N1 和 N2 是多重集的大小。

链接：

set_difference: https://en.cppreference.com/w/cpp/algorithm/set_difference

编译器资源管理器：https://godbolt.org/z/o3KGbf

Answer 4

问题可以在 O(nlogn) 时间复杂度内解决。

算法

Sort both array with merge sort in O(nlogn) complexity. You can also use sort-function. For example sort(array1.begin(),array1.end()).
Now use two pointer method to remove all common elements on both arrays.
上述方法的程序

    int i = 0, j = 0; 
    while (i < array1.size() && j < array2.size()) { 
  
        // If not common, print smaller 
        if (array1[i] < array2[j]) { 
            cout << array1[i] << " "; 
            i++; 
        } 
        else if (array2[j] < array1[i]) { 
            cout << array2[j] << " ";  
            j++; 
        } 

        // Skip common element 
        else { 
            i++; 
            j++; 
        } 
    }

以上程序的复杂度为O(array1.size() + array2.size())。在最坏的情况下说 O(2n)
上面的程序给出了不常见的元素作为输出。如果你想存储它们，只需创建一个向量并将它们推入向量。
原题LINK

使用哈希查找不常见的元素

Find uncommon elements using hashing

c++

arrays

hash

hashset

c++14