Come si trova il primo elemento comune in due matrici

L'ordinamento degli array non funzionerà. Modificando l'ordine non sarai in grado di determinare quale elemento corrisponde per primo.

Anche la soluzione intersect non funzionerà. Per usarlo dovresti copiare entrambi gli array in una classe impostata, che per definizione non conserva l'ordine.

La tua risposta è corretta. Vorrei prendere in considerazione l'utilizzo di hashset per ridurre i tempi di ricerca.

Se il problema è trovare il primo elemento della lista L1 che è anche contenuto in L2, scorrere gli elementi di L1 uno alla volta e controllare se l'elemento corrente è in L2. Il secondo test ("è un elemento in L2") può essere fatto da un semplice ciclo su tutti gli elementi in L2. Oppure metti prima tutti gli elementi di L2 in un hashset, il che può velocizzare il processo in modo equo.

Ora dovrebbe essere ovvio che puoi cambiare i ruoli di L1 e L2 quando stai cercando il primo elemento in L2 che è anche parte di L1. E se stai cercando un elemento comune da uno degli elenchi che ha l'indice posizionale più basso in L1 o L2, esegui entrambi i passaggi descritti finora, e se trovi due elementi diversi, scegli quello con l'indice più basso in entrambi L1 o L2.

Questo approccio ha uno svantaggio: se L1 e L2 sono enormi, e hai alcuni elementi non comuni all'inizio di ogni lista, devi leggere l'elenco completo L1, L2 o entrambi, anche quando ci sono alcuni elementi comuni tra i primi elementi di L1 e L2. Quindi l'idea della tua soluzione sopra è quella di utilizzare i seguenti sottoinsiemi:

K1(n)="the first n elements of L1" (or L1 if n>length(L1))
K2(n)="the first n elements of L2" (or L2 if n>length(L2))

con n che va da 1 a max(length(L1),length(L2) e controlla se K1 e K2 hanno un elemento comune, per ogni n. Il più piccolo n dove K1 (n) e K2 (n) hanno elementi comuni mostra che l'n-esimo elemento di L1 o l'n-esimo elemento di L2 è l'elemento che stai cercando.

Dovrebbe essere ovvio che quando K1 (n) e K2 (n) sono disgiunti, e stai andando da n a n + 1, devi solo controllare se i nuovi elementi di n+1 st introdotti da L1 e L2 sono in K2 (n + 1) o K1 (n + 1). L'uso di una veloce struttura dati hashset per K1 e K2 che è estesa in modo incrementale mantiene questo processo veloce anche per n più grandi. E se hai trovato un elemento comune per un certo n, puoi interrompere immediatamente il processo. Questo è quello che hai descritto nel tuo post.

Questo approccio funzionerà abbastanza velocemente anche se L1 e L2 hanno, per esempio, più di un milione di elementi, ma il primo elemento comune in entrambi gli elenchi è tra i "primi dieci" in entrambi gli elenchi. Non ti farà risparmiare molto quando L1 e L2 non hanno alcun elemento in comune, ma questo vale anche per qualsiasi altro approccio.

Dire che il primo array A ha lunghezza n e il secondo array B ha lunghezza m.

Qualunque sia la più piccola lunghezza, passane in loop e metti i suoi elementi in un LinkedHashSet (non importa se è ordinato o non ordinato). Quindi esegui un ciclo attraverso il secondo array e interroga il set per quell'elemento. Ovunque tu trovi il tuo primo elemento comune, rompi.

Complessità spaziale: O (m) assumendo m è minore o uguale a n Complessità del tempo: O (n)

//Java-like pseudo code
class FirstCommonFinder {
    Element[] firstInput = {….};
    Element[] secondInput = {….};
    Set smallerInput = new LinkedHashSet<>();
    boolean found = false;
    //assuming firstInput is smaller than secondInput
    for (Element input: firstInput) {
        smallerInput.add(input);
    }

    //loop through and break upon first common occurrence 
    for (int i = 0; i < secondInput.length; i++) {
        if (smallerInput.contains(secondInput[i])) {
        found = true;
        break;
    }
}


} 
  

Nel caso in cui se si desidera tenere traccia degli indici in entrambi gli array di input (per elementi comunemente presenti), utilizzare una LinkedHashMap e inserire l'indice dell'array come valore sulla chiave dell'elemento.

Personalmente, penso che la soluzione impostata funzioni, ma se si desidera ottimizzare la soluzione con l'utilizzo della memoria O (1), è possibile invertire i due elenchi, che saranno O (n), quindi iniziare dall'inizio, usare due puntatori, trova la prima differenza e il nodo appena prima della differenza è la risposta. E se non ti consente di modificare l'elenco originale, puoi tornare indietro. Che è ancora O (n).

Questo è un Set Intersect . In .NET, penso che possa essere usato il metodo LINQ Intersect (). Java e altri dovrebbero averne uno.

Si noti che è necessario fare attenzione se l'implementazione preserva l'ordine dell'indice dell'array. Per esempio. in .NET, chiamare First () potrebbe non restituire il primo per ordine dell'indice di array.

Per l'implementazione di basso livello di un Set Intersect, avrei bisogno di consultare un libro di Algorithms. :)