在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语言，需要一份易于理解的说明文档，而非代码示例。

- Iskar Jarak

Answer 1

你已经有了两个数组的交集逻辑，所以只需多次调用它即可。 你的交集逻辑，

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

将上述代码封装在一个名为Intersect(int[] array1, int[] array2, int array1Length, int array2Length)的函数中，该函数返回int[]。在结果上再次调用此方法。

• 调用1: int[] result = Intersect(array1, array2, array1Length, array2Length)
• 调用2: result = Intersect(result, array3, resultArrayLength, array3Length)
• ...
• 调用(n-1): result = Intersect(result, arrayn, resultArrayLength, arraynLength)

可能的优化：

• 仅当resultArrayLength > 0时才继续调用（否则交集为空集）。
• 在intersect方法中，将array1的最后一个元素与array2的第一个元素进行比较，即

已编辑 if (array1[array1Length - 1] < array2[0]) 返回空集（假设数组已排序）。

- Devendra D. Chavan

---

如果你的数组非常大，比如每个数组都有超过2000个元素，那么这种方法效率非常低下，因为你需要对每个数组中的所有元素进行比较。优化方法2是一个好点子，但在实际情况下并不经常发生。 - zookastos

Answer 2

我假设你的所有数组都是有序的。我们假设有数组 A_1 到 A_n。为每个数组设置一个计数器（因此，我们有 n 个计数器 i_1 到 i_n，就像你为两个数组所做的那样）。 现在，我们引入一个最小堆，以这样的方式包含整个数组，即最小数组是由相应指针指向的当前最低数字的数组。这意味着，我们可以在任何时候检索当前指向最低数字的数组。 现在，我们从堆中提取最小数组并记住它。只要指向的数字保持不变，我们就继续提取最小数组。如果我们提取了 所有 数组（即如果所有数组都具有相同的当前最低指向数字），则我们知道该数字在交集中。如果不是（即如果并非所有数组都包含相同的当前最低指向数字），则我们知道我们当前正在检查的数字不能在交集中。因此，我们将已提取的所有数组的计数器增加，并将它们放回堆中。 我们重复以上步骤，直到找到一个数组的指针达到该数组的末尾。对于描述不够详细，我很抱歉，但我没有足够的时间进行更详细的说明。

编辑。

如果你有一个非常少元素的数组，那么仅使用二分搜索其他数组中的这些数字或使用哈希表检查这些数字可能是有用的。

- phimuemue

---

您的描述已经足够详细了，但是我仍然在努力分析这种方法的成本与重复的双向交叉口相比较。您对此有何想法？ - Iskar Jarak

Answer 3

我会先求出两个最小的数组的交集，然后将结果与剩下的最小交集数组继续求交集。这样可以保证每次交集中的两个数组之一都不会比原始最小数组更大，从而节省时间。

- shelman

---

那可能是一个非常有用的提示。 - phimuemue

Answer 4

使用合并排序的方法。

让数组为

1 2 3 4 5 6 7。

首先找到 1 2，2 4，5 6 的交集，对于 7 不进行任何操作。 新集合：A（1-2 交集）B（3-4 交集）C（5-6 交集）7。 重复以上步骤直到获得一个集合。

- sunmoon

Answer 5

由于交集操作是可交换和可结合的，因此您可以将计算并行化。让每个线程计算两个数组的交集，这将在每个步骤中将数组数量减少两个。

- Sylvain Defresne

Answer 6

如果对空间复杂度没有限制，那么使用哈希表就很容易实现。假设数组中不存在重复的数字。 以下是相应的Python代码：

def intersection(arr_list):
    """
    >>> intersection([[1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6]])
    [3, 4]
    >>> intersection([[1, 2, 3, 4], [2, 3, 4, 5], [5, 6]])
    []
    """
    n = len(arr_list)
    ret = []
    d = {}
    for i in arr_list[0]:
        d[i] = 1
    for arr in arr_list[1:]:
        for j in arr:
            if j in d:
                d[j] += 1
    for k, v in d.items():
        if v == n:
            ret.append(k)
    return ret

if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=True)

- Vijayendra Bapte