Algorithme efficace pour produire l'intersection à n voies de tableaux triés en C

Question

J'ai besoin de produire l'intersection entre des tableaux triés d'entiers en C. Je sais comment trouver l'intersection entre deux tableaux triés, mais j'ai besoin de le faire pour plus de deux tableaux, efficacement et sans connaissance préalable du nombre de tableaux. Je peux imposer une limite raisonnable au nombre maximal - disons dix pour l'instant. Ces tableaux peuvent compter de quelques éléments à plusieurs centaines de milliers d'éléments, et ne sont pas nécessairement de la même longueur.

Pseudo-code pour produire l'intersection de deux tableaux triés :

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

Je travaille en C, et je cherche une explication claire plutôt que du code.

Answer 1

S'il n'y a pas de contrainte sur la complexité de l'espace, il sera facile d'y parvenir en utilisant un hashmap. En supposant que les nombres ne sont pas répétés dans un même tableau.

Voici le code python pour la même chose :

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)