Jak skutecznie sprawdzić, czy dwie listy zawierają elementy uporządkowane w ten sam sposób?

Question

Mam dwie uporządkowane listy tego samego typu elementu, każda lista ma co najwyżej jeden element każdej wartości (np. Liczby własne i unikalne), ale poza tym bez żadnych ograniczeń (jedna może być podzbiorem drugiej, mogą być całkowicie disjunct lub udostępniać niektóre elementy, ale nie inne).

Jak skutecznie sprawdzić, czy A zamawia dwa dowolne elementy w inny sposób niż B? Na przykład, jeśli A ma pozycje 1, 2, 10 i B pozycje 2, 10, 1, własność nie będzie miała wartości A jako listy 1 przed 10, ale B wymienia ją po 10, 1, 2, 10 kontra 2, 10 5 byłoby całkowicie poprawne, jednak ponieważ A nigdy w ogóle nie wspomina o 5, nie mogę polegać na żadnej z wymienionych reguł sortowania.

Answer 1

Możesz otrzymać O (n) w następujący sposób. Najpierw znajdź przecięcie dwóch zestawów za pomocą mieszania. Po drugie, sprawdź, czy A i B są identyczne, jeśli rozważasz tylko elementy ze skrzyżowania.

Answer 2

Moje podejście byłoby najpierw zrobić posortowanych kopii A i B który również nagrywać położeń elementów w oryginalnych list:

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) 

teraz znaleźć te elementy wspólne z użyciem standardowej listy seryjnej, który rejestruje pozycje w obu A i B ze wspólnych elementów:

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 

Wreszcie porządek shared przez jej pierwszego elementu (pozycja w A) i sprawdź, czy wszystkie jego drugie elementy (pozycje w B) rosną. Będzie to miało miejsce w przypadku IFF elementów wspólnych A i B się w tym samym porządku:

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 

Złożoność 2 * (O (n) + O (nlog n)) + O (n) + O (nlog n) + O (n) = O (nlog n).

Answer 3

Ogólne podejście: przechowuj wszystkie wartości i ich pozycje w B jako klucze i wartości w HashMap. Iteruj wartości w A i sprawdź je w HashMapie B, aby uzyskać ich pozycję w B (lub zerowej). Jeśli ta pozycja to przed największą wartością pozycji, jaką widziałeś wcześniej, to wiesz, że coś w B jest w innej kolejności niż A. Działa w czasie O (n).

Szorstki, kod całkowicie niesprawdzone:

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