Come posso determinare in modo efficiente se due elenchi contengono elementi ordinati allo stesso modo?

Question

Ho due elenchi ordinati dello stesso tipo di elemento, ogni elenco con al massimo un elemento di ogni valore (ad esempio int e numeri univoci), ma altrimenti senza restrizioni (uno può essere un sottoinsieme dell'altro, possono essere completamente disgiunti o condividi alcuni elementi ma non altri).

Come determinare in modo efficiente se A ordina due elementi in modo diverso da B? Ad esempio, se A ha gli articoli 1, 2, 10 e B gli articoli 2, 10, 1, la proprietà non si manterrà come A liste 1 prima di 10 ma B la elenca dopo 10. 1, 2, 10 vs 2, 10 , 5 sarebbe perfettamente valido, tuttavia, poiché A non menziona mai 5, non posso contare su alcuna regola di ordinamento condivisa da entrambe le liste.

Answer 1

È possibile ottenere O (n) come segue. Innanzitutto, trova l'intersezione dei due set usando l'hashing. Secondo, verifica se A e B sono identici se consideri solo gli elementi dall'intersezione.

Answer 2

Il mio approccio sarebbe quello di fare prima copie fascicolate di A e B che registrano anche le posizioni degli elementi nelle liste originali:

for i in 1 .. length(A): 
    Apos[i] = (A, i) 
sortedApos = sort(Apos[] by first element of each pair) 

for i in 1 .. length(B): 
    Bpos[i] = (B, i) 
sortedBpos = sort(Bpos[] by first element of each pair) 

Ora trovare quegli elementi in comune con una lista merge standard che registra il posizioni sia A e B degli elementi comuni:

i = 1 
j = 1 
shared = [] 
while i <= length(A) && j <= length(B) 
    if sortedApos[i][1] < sortedBpos[j][1] 
     ++i 
    else if sortedApos[i][1] > sortedBpos[j][1] 
     ++j 
    else // They're equal 
     append(shared, (sortedApos[i][2], sortedBpos[j][2])) 
     ++i 
     ++j 

Infine, ordina shared dal suo primo elemento (posizione in A) e verificare che tutti i suoi secondi elementi (posizioni in B) aumentino. Questo sarà il caso se e solo se gli elementi comuni a A e B apparire nello stesso ordine:

sortedShared = sort(shared[] by first element of each pair) 
for i = 2 .. length(sortedShared) 
    if sortedShared[i][2] < sortedShared[i-1][2] 
     return DIFFERENT 

return SAME 

Complessità: 2 * (O (n) + O (nlog n)) + O (n) + O (nlog n) + O (n) = O (nlog n).

Answer 3

Approccio generale: memorizza tutti i valori e le loro posizioni in B come chiavi e valori in una HashMap. Scorrere i valori in A e cercarli nella HashMap di B per ottenere la loro posizione in B (o null). Se questa posizione è prima del il valore di posizione più grande che hai visto in precedenza, allora sai che qualcosa in B è in un ordine diverso da A. Esegue l'ora O (n).

Ruvido, il codice non testato totalmente:

boolean valuesInSameOrder(int[] A, int[] B) 
{ 
    Map<Integer, Integer> bMap = new HashMap<Integer, Integer>(); 
    for (int i = 0; i < B.length; i++) 
    { 
    bMap.put(B[i], i); 
    } 

    int maxPosInB = 0; 
    for (int i = 0; i < A.length; i++) 
    { 
    if(bMap.containsKey(A[i])) 
    { 
     int currPosInB = bMap.get(A[i]); 
     if (currPosInB < maxPosInB) 
     { 
     // B has something in a different order than A 
     return false; 
     } 
     else 
     { 
     maxPosInB = currPosInB; 
     } 
    } 
    } 

    // All of B's values are in the same order as A 
    return true; 
}