¿Cómo puedo determinar de manera eficiente si dos listas contienen elementos ordenados de la misma manera?

Question

Tengo dos listas ordenadas del mismo tipo de elemento, cada lista tiene como máximo un elemento de cada valor (digamos enteros y números únicos), pero sin restricciones (uno puede ser un subconjunto del otro, pueden estar completamente disyunción, o compartir algunos elementos pero no otros).

¿Cómo puedo determinar de manera eficiente si A está ordenando dos elementos de una manera diferente a B? Por ejemplo, si A tiene los ítems 1, 2, 10 y B los ítems 2, 10, 1, la propiedad no se mantendría como A lista 1 antes que 10 pero B lo lista después de 10. 1, 2, 10 contra 2, 10 , 5 sería perfectamente válido, sin embargo, como A nunca menciona 5 en absoluto, no puedo confiar en ninguna regla de clasificación dada compartida por ambas listas.

Answer 1

Puede obtener O (n) de la siguiente manera. Primero, encuentra la intersección de los dos conjuntos usando hash. En segundo lugar, compruebe si A y B son idénticos si solo considera elementos de la intersección.

Answer 2

Mi enfoque sería hacer primero copias clasificadas de A y B que también registran las posiciones de los elementos de las listas originales:

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) 

Ahora encontrar esos elementos en común el uso de una combinación de lista estándar que registra la posiciones en ambos A y B de los elementos compartidos:

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 

Finalmente, tipo shared por su primer elemento (posición en A) y compruebe que todos sus segundos elementos (posiciones en B) están aumentando. Este será el caso si y sólo si los elementos comunes a A y B aparecer en el mismo orden:

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 

complejidad Tiempo: 2 * (O (n) + O (n log n)) + O (n) + O (nlog n) + O (n) = O (nlog n).

Answer 3

Enfoque general: almacene todos los valores y sus posiciones en B como claves y valores en un HashMap. Iterate sobre los valores en A y búscalos en HashMap de B para obtener su posición en B (o nulo). Si esta posición es antes de el valor de posición más grande que haya visto anteriormente, entonces sabrá que algo en B está en un orden diferente que A. Se ejecuta en el tiempo O (n).

áspero, código totalmente no probado:

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; 
}