cómo Y una gran cantidad de matrices de números?

Question

Tengo 200 matrices de enteros positivos clasificados (algunos de ellos tienen más de un millón de números). Necesito encontrar el primer número que existe en cada matriz. ¿Qué sugieres?

Answer 1

• Mantenga un índice en cada matriz.
• Comience con el primer número del primer conjunto como referencia.
• Es el primer número de la matriz n-ésima más baja que la referencia, aumente su índice.
• Es el primer número de la n-ésima matriz igual a la referencia, aumente ny continúe con - la siguiente matriz.
• Es el primer número de la matriz n-ésima más alta que la referencia, use ese número como referencia y comience nuevamente.
• Si n == 201, su referencia existe en todas las matrices.

Editar: un ejemplo de código:

while n < len(data): 
    item = data[n][indices[n]] 
    if item < reference: 
     indices[n] += 1 
    elif item == reference: 
     n += 1 
    elif item > reference: 
     reference = item 
     n = 0 

print reference 

Answer 2

Puede hacer una combinación de k-way en las matrices y buscar el primer elemento que aparece k veces.

Una alternativa es crear un histogram, y eligió el primer elemento que aparece k en el histograma. Un histograma en Java puede ser implementado fácilmente por un Map<Element,Integer>

Ambas soluciones son O(kn) donde k es el número de matrices y n es el tamaño promedio de una matriz, por lo que básicamente es lineal en el tamaño de la entrada.