更快速地搜索数组

Question

我有一个包含100,000套的数组.每组包含低于1,000,000的自然数.我必须找到有序对{m,n}的数量,其中0 <m <1,000,000,0 <n <1,000,000和m!= n,它们在100,000个集合中的任何一个中都不存在.搜索所有集合的简单方法导致10 ^ 5*(10 ^ 6选择2)个搜索次数.

例如,我有2套set1 = {1,2,4} set2 = {1,3}.所有可能的有序数字对低于5是{1,2},{1,3},{1,4},{2,3},{2,4}和{3,4}.在集合1中不存在的低于5的有序数字对是{1,3},{2,3}和{3,4}.第2组中低于5的有序对是{1,2},{1,4},{2,3},{2,4}和{3,4}.在两个集合中不存在的有序对是{2,3}和{3,4}.因此,缺失的有序对的数量是2.

任何人都能指出我一种聪明的方式来组织我的数据结构,以便找到丢失的对的数量更快？如果之前已经提出这个问题,我会提前道歉.

更新:以下是有关数据集结构的一些信息.每组中的元素数量从2到500,000不等.元素的中位数约为10,000.分布在10,000左右达到峰值并向两个方向逐渐减小.100,000套元素的联合接近1,000,000.

Answer 1

作为一个选项，您可以在您的集合上构建布隆过滤器。

在检查所有集合之前，您可以快速查找布隆过滤器，因为它永远不会产生误报，所以您可以安全地使用您的对，因为它不存在于您的集合中。