查找大小为n的两个集合A和B之差的算法 [英] An algorithm to find the difference of two set A and B with size n

问题描述

有两个集合A和B，两个集合的大小均为n.如何用O(n)查找A中不在B(A-B)中的每个元素.我应该使用哪种数据结构(bloom过滤器?)

There are two set A and B, and the size of both sets is n. How to find every elements of A that is not in B (A-B), with O(n). What data structure should I use (bloom filter?)

推荐答案

鉴于两者都是集合，您应该使用集合/哈希集.这将让您计算O(1)中的contains/in操作.布隆过滤器不适用于此类问题-它们会告诉您某个元素是否绝对不在一组对象中，但仍有可能出现误报.最好使用常规的哈希集，因为您想要一个准确的答案.

Given that both are sets, you should use a set / hashset. This will let you compute the contains / in operation in O(1). Bloom filters aren't good for this type of problem - they tell you if an element definitely isn't in a set of objects, but there are still chances for false positives. You're better off using a regular hashset since you want an exact answer.

给出两个集合，您可以在O(min(|A|, |B|))中计算集合差异.

Given two sets you can compute the set difference in O(min(|A|, |B|)).

如果A是较小的集合，则可以遍历A中的所有元素，并丢弃B中存在的元素.

If A is the smaller set you can loop through all elements in A and discard the ones that are present in B.

如果B是较小的集合，则可以遍历B中的所有元素，并丢弃(从集合A中)在A中找到的任何元素.

If B is the smaller set you can loop through all the elements in B and discard (from set A) any one you find in A.

这篇关于查找大小为n的两个集合A和B之差的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！