Znajdź wspólne elementy w N posortowanych tablicach bez dodatkowej przestrzeni

Question

Biorąc pod uwagę N tablic o rozmiarze N i wszystkie są posortowane, jeśli nie pozwala ci na użycie dodatkowej przestrzeni, w jaki sposób znajdziesz ich wspólne dane wydajnie lub z mniejszą złożonością czasu ?

Dla ex:

1. 10 160 200 500 500 
2. 4 150 160 170 500 
3. 2 160 200 202 203 
4. 3 150 155 160 300 
5. 3 150 155 160 301 

To pytanie wywiad, znalazłem kilka pytań, które były podobne, ale nie obejmują dodatkowych warunków wejścia są sortowane ani nie jest w stanie korzystać z dodatkowej pamięci.

Nie mogłem wymyślić żadnego rozwiązania mniejszego niż złożoność O (n^2 lg n). W tym przypadku wolałbym iść z najprostszego rozwiązania, które daje mi tej złożoności, który jest:

not_found_flag = false 

    for each element 'v' in row-1 
     for each row 'i' in the remaining set 
      perform binary search for 'v' in 'i' 
      if 'v' not found in row 'i' 
       not_found_flag = true 
       break 
     if not not_found_flag 
      print element 'v' as it is one of the common element 

Możemy to poprawić poprzez porównanie wartości minimalne i maksymalne w każdym rzędzie i zdecydować, czy na podstawie tego, że jest możliwe, aby liczba "num" mieściła się między "min_num" a "max_num" tego wiersza.

Przeszukiwanie binarne -> O (log n) Do przeszukiwania 1 num do n-1, wiersze: O (nlogn) binarne wyszukiwania dla każdej liczby z pierwszego rzędu: O (n2logn)

I wybrany pierwszym rzędzie możemy wybrać dowolny wiersz i jeśli w żadnym z wierszy (N-1) nie znaleziono żadnego elementu wybranego wiersza, to tak naprawdę nie mamy wspólnych danych.

Answer 1

Wygląda na to, że można to zrobić w O(n^2); tj. wystarczy spojrzeć na każdy element jeden raz. Zauważ, że jeśli element jest wspólny dla wszystkich tablic, to musi istnieć w dowolnym z nich. Również dla celów ilustracji (i od kiedy użyłeś pętli for powyżej), zakładam, że możemy zachować indeks dla każdej z tablic, ale porozmawiam o tym, jak obejść to później.

Nazwijmy tablice A_1 przez A_N i używać indeksów zaczynając od 1. pseudokod:

# Initial index values set to first element of each array 
for i = 1 to N: 
    x_i = 1 

for x_1 = 1 to N: 
    val = A_1[x_1] 
    print_val = true 
    for i = 2 to N: 
    while A_i[x_i] < val: 
     x_i = x_i + 1 
    if A_i[x_i] != val: 
     print_val = false 
    if print_val: 
    print val 

Wyjaśnienie algorytmu. Używamy pierwszej tablicy (lub dowolnej dowolnej tablicy) jako algorytmu odniesienia i iterujemy równolegle wszystkie inne macierze (rodzaj jak krok scalania sortowania scalonego, z wyjątkiem tablic N). Każda wartość tablicy referencyjnej wspólne dla wszystkich tablic musi być obecne we wszystkich pozostałych tablicach. Tak więc dla każdej innej tablicy (ponieważ są one sortowane), zwiększamy indeks x_i, aż wartość tego indeksu A_i[x_i] jest co najmniej wartością, której szukamy (nie interesują nas mniejsze wartości, nie mogą być wspólne.) Możemy to zrobić, ponieważ tablice są sortowane, a więc monotonnie nierównomierne. Jeśli wszystkie macierze mają tę wartość, wydrukujemy ją, w przeciwnym razie zwiększamy x_1 w tablicy referencyjnej i kontynuujemy. Musimy to zrobić, nawet jeśli nie wydrukujemy wartości.

Pod koniec wydrukowaliśmy wszystkie wartości wspólne dla wszystkich tablic, a tylko raz zbadaliśmy każdy element.

Obejście wymogu dodatkowej pamięci. Jest wiele sposobów na zrobienie tego, ale myślę, że najprościej byłoby sprawdzić pierwszy element każdej tablicy i przyjąć max jako tablicę referencyjną A_1. Jeśli wszystkie są takie same, wypisz tę wartość, a następnie zapisz indeksy x_2 ... x_N jako pierwszy element każdej z nich.

implementacja Javy (dla zwięzłości, bez dodatkowego włamania), przy użyciu przykładowego wejścia:

public static void main(String[] args) { 
    int[][] a = { 
      { 10, 160, 200, 500, 500, }, 
      { 4, 150, 160, 170, 500, }, 
      { 2, 160, 200, 202, 203, }, 
      { 3, 150, 155, 160, 300 }, 
      { 3, 150, 155, 160, 301 } }; 

    int n = a.length; 
    int[] x = new int[n]; 

    for(; x[0] < n; x[0]++) { 
     int val = a[0][x[0]]; 
     boolean print = true; 
     for(int i = 1; i < n; i++) { 
      while (a[i][x[i]] < val && x[i] < n-1) x[i]++;    
      if (a[i][x[i]] != val) print = false;    
     } 
     if (print) System.out.println(val); 
    } 
} 

wyjściowy:

160 

Answer 2

O (n^2) (Python) wersję, która nie robi Użyj dodatkowej pamięci, ale zmodyfikuj oryginalną tablicę. Pozwala na przechowywanie wspólnych elementów bez ich drukowania:

data = [ 
    [10, 160, 200, 500, 500], 
    [4, 150, 160, 170, 500], 
    [2, 160, 200, 202, 203], 
    [3, 150, 155, 160, 300], 
    [3, 150, 155, 160, 301], 
] 

for k in xrange(len(data)-1): 
    A, B = data[k], data[k+1] 
    i, j, x = 0, 0, None 

    while i<len(A) or j<len(B): 
     while i<len(A) and (j>=len(B) or A[i] < B[j]): 
      A[i] = x 
      i += 1 

     while j<len(B) and (i>=len(A) or B[j] < A[i]): 
      B[j] = x 
      j += 1 

     if i<len(A) and j<len(B): 
      x = A[i] 
      i += 1 
      j += 1 

print data[-1] 

Co robię jest w zasadzie dostać każdą tablicę w danych i porównywanie z nim dalej, element po elemencie, usuwając te, które nie są wspólne.

Answer 3

Jest to rozwiązanie w Pythonie O(n^2), nie zużywa dodatkowej przestrzeni, ale niszczy list:

def find_common(lists): 
    num_lists = len(lists) 
    first_list = lists[0] 
    for j in first_list[::-1]: 
     common_found = True 
     for i in range(1,num_lists): 
      curr_list = lists[i] 
      while curr_list[len(curr_list)-1] > j: 
       curr_list.pop() 
      if curr_list[len(curr_list)-1] != j: 
       common_found = False 
       break 
     if common_found: 
      return j 

Answer 4

Oto wykonania Java

public static Integer[] commonElementsInNSortedArrays(int[][] arrays) { 
    int baseIndex = 0, currentIndex = 0, totalMatchFound= 0; 
    int[] indices = new int[arrays.length - 1]; 
    boolean smallestArrayTraversed = false; 
    List<Integer> result = new ArrayList<Integer>(); 
    while (!smallestArrayTraversed && baseIndex < arrays[0].length) { 
     totalMatchFound = 0; 
     for (int array = 1; array < arrays.length; array++) { 
      currentIndex = indices[array - 1]; 
      while (currentIndex < arrays[array].length && arrays[array][currentIndex] < arrays[0][baseIndex]) { 
       currentIndex ++;      
      } 

      if (currentIndex < arrays[array].length) { 
       if (arrays[array][currentIndex] == arrays[0][baseIndex]) { 
        totalMatchFound++; 
       } 
      } else { 
       smallestArrayTraversed = true; 
      } 
      indices[array - 1] = currentIndex; 
     } 
     if (totalMatchFound == arrays.length - 1) { 
      result.add(arrays[0][baseIndex]); 
     } 
     baseIndex++; 
    } 

    return result.toArray(new Integer[0]); 
} 

Oto Jednostka Testy

@Test 
public void commonElementsInNSortedArrayTest() { 
    int arr[][] = { {1, 5, 10, 20, 40, 80}, 
        {6, 7, 20, 80, 100}, 
        {3, 4, 15, 20, 30, 70, 80, 120} 
        }; 

    Integer result[] = ArrayUtils.commonElementsInNSortedArrays(arr); 
    assertThat(result, equalTo(new Integer[]{20, 80})); 

    arr = new int[][]{ 
      {23, 34, 67, 89, 123, 566, 1000}, 
      {11, 22, 23, 24,33, 37, 185, 566, 987, 1223, 1234}, 
      {23, 43, 67, 98, 566, 678}, 
      {1, 4, 5, 23, 34, 76, 87, 132, 566, 665}, 
      {1, 2, 3, 23, 24, 344, 566} 
      }; 

    result = ArrayUtils.commonElementsInNSortedArrays(arr); 
    assertThat(result, equalTo(new Integer[]{23, 566})); 
}