come AND un gran numero di matrici di numeri?

Question

Ho 200 matrici di interi positivi ordinati (alcuni di loro hanno più di un milione di numeri). Devo trovare il primo numero esistente in ogni array. Che cosa suggeriresti?

Answer 1

• Mantiene un indice su ogni matrice.
• Iniziare con il primo numero del primo array come riferimento.
• È il primo numero dell'array n-esimo inferiore al riferimento, aumenta il suo indice.
• È il primo numero dell'array n-esimo uguale al riferimento, aumentare n e procedere con - l'array successivo.
• È il primo numero dell'array n-th superiore al riferimento, utilizzare quel numero come riferimento e ricominciare.
• Se n == 201, il riferimento esiste in ogni matrice.

Edit: un esempio di codice:

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

È possibile eseguire un'unione k-way sugli array e controllare il primo elemento che appare k volte.

Un'alternativa è la creazione di un histogram e ha scelto il primo elemento che appare ora k nell'istogramma. Un istogramma in java può essere implementata facilmente da un Map<Element,Integer>

Entrambe le soluzioni sono O(kn) dove k è il numero di matrici e n è la dimensione media di una matrice, quindi è sostanzialmente lineare nella dimensione dell'input.