高效的算法,用于在C中生成排序数组的n路交集

Question

我需要在C中生成一些排序的整数数组之间的交集.我知道如何找到两个排序数组之间的交集,但我需要为两个以上的数组执行此操作,有效且无需事先了解数组的数量.我可以对最大数量施加合理的限制 - 现在就说十.这些阵列可以是从几个项目到几十万个项目的任何地方,并且绝不一定是相同的长度.

用于生成两个排序数组的交集的伪代码:

while i < m and j < n do:
    if array1[i] < array2[j]:
        increment i
    else if array1[i] > array2[j]: 
        increment j
    else 
        add array1[i] to intersection(array1, array2)
        increment i
        increment j

我正在和C一起工作,我的解释清楚而不是代码.

Answer 1

我假设你的所有数组都已排序。假设我们有A_1数组A_n。每个数组都有一个计数器（因此，我们有 的计数器n，就像您对两个数组所做的那样）。i_1i_n

现在我们引入一个最小堆，它以某种方式包含整个数组，使得最小数组是相应指针指向的当前最小数字的数组。这意味着，我们可以在每个时刻检索当前指向的最小数字的数组。

现在，我们从堆中提取最小数组并记住它。只要指向的数字保持不变，我们就继续提取最小数组。如果我们提取所有数组（即，如果所有数组具有相同的当前最低指向数字），我们就知道该数字位于交集内。如果不是（即，如果并非所有数组都包含相同的当前最低指向数字），我们就知道我们当前正在检查的数字不能位于交集内。因此，我们将所有计数器增加到已提取的数组并将它们放回堆中。

我们这样做，直到找到一个数组的指针到达数组的末尾。我很抱歉描述不详细，但我没有足够的时间来更详细地解决它。

编辑。

如果您有一个包含很少元素的数组，则仅在其他数组中二进制搜索这些数字或使用哈希表检查这些数字可能会很有用。