Jak przecinać dwie posortowane liczby całkowite bez duplikatów?

Question

To jest pytanie do wywiadu, którego używam jako ćwiczenia programistyczne.

Wejście: dwa posortowane tablice całkowite A i B w rosnącej kolejności i różne rozmiary N i M odpowiednio

wyjściowa: posortowanej tablicy całkowitą C w porządku rosnącym, która zawiera elementy, które są dostępne w obu a i B

contraints: duplikaty nie są dozwolone C

Przykład: dla wejścia A = {3,6,8,9} i B = {4,5,6,9,10,11}, wynik powinien wynosić C = {6,9}

Dziękuję za odpowiedzi, wszystkie ! Podsumowując, istnieją dwa główne podejścia do tego problemu:

Moim oryginalnym rozwiązaniem było zachowanie dwóch wskaźników, po jednym dla każdej macierzy i skanowanie z lewej do prawej strony zamiennie, podczas wybierania pasujących elementów. Kiedy więc bieżący element jednej tablicy jest większy niż druga, ciągle zwiększamy wskaźnik drugiej tablicy, dopóki nie znajdziemy bieżącego pierwszego elementu tablicy lub nie przekroczymy go (znajdź większy). Wszystkie pasują do osobnej tablicy, która jest zwracana po dojściu do końca jednej z tablic wejściowych.

Innym sposobem, w jaki możemy to zrobić, jest przeskanowanie jednej z tablic liniowo, podczas korzystania z wyszukiwania binarnego, aby znaleźć dopasowanie w drugiej tablicy. To by oznaczało czas O (N * log (M)), jeśli skanujemy A i dla każdego z jego wyszukiwania binarnego N elementów na B (czas O (log (M)).

Zaimplementowałem oba podejścia i przeprowadziłem eksperyment, aby zobaczyć, jak te dwie rzeczy są porównywane (szczegóły na ten temat można znaleźć here). Metoda Binary Search wydaje się wygrywać, gdy M jest około 70 razy większa niż N, gdy N ma 1 milion elementów.

Answer 1

Problem zasadniczo sprowadza się do operacji przyłączenia a następnie filtr operacji (w celu usunięcia duplikaty i tylko utrzymać wewnętrzną wyników).

Ponieważ dane wejściowe są już posortowane, łączenie można skutecznie uzyskać poprzez merge join, z O (size (a) + size (b)).

Operacja filtra będzie O (n), ponieważ wyjście sprzężenia zostanie posortowane, a w celu usunięcia duplikatów wystarczy sprawdzić, czy każdy element jest taki sam jak przed nim. Filtrowanie tylko wewnętrznych dopasowań jest trywialne, po prostu odrzucasz wszystkie elementy, które nie zostały dopasowane (zewnętrzne sprzężenia).

Istnieją możliwości równoległości (zarówno w sprzężeniu, jak i filtrowaniu) w celu uzyskania lepszej wydajności. Na przykład framework Apache Pig w Hadoop oferuje parallel implementation łączenia łączenia.

Istnieją oczywiste kompromisy między wydajnością i złożonością (a tym samym łatwością obsługi). Powiedziałbym więc, że dobra odpowiedź na pytanie z wywiadu naprawdę musi uwzględniać wymagania dotyczące wydajności.

• Zestawienie oparte na zestawie - O (nlogn) - Względnie powolne, bardzo proste, należy użyć, jeśli nie występują problemy z wydajnością. Prostota wygrywa.

• Łączenie łączenia + Filtrowanie - O (n) - Szybkie, podatne na błąd kodowania, należy użyć, jeśli wydajność jest . Najlepiej spróbuj wykorzystać istniejącą bibliotekę, aby to zrobić, a może nawet użyj bazy danych, jeśli jest taka potrzeba.

• Parallel Wdrożenie - O (n/p) - Bardzo szybko, wymaga innej infrastruktury w miejscu, używać, jeśli objętość jest bardzo duże i przewiduje się rozwijać i to jest głównym wydajność gardłem.

(również pamiętać, że funkcja w pytaniu intersectSortedArrays jest zasadniczo zmodyfikowane seryjnej dołączyć, gdzie filtr jest zrobione podczas łączenia. Można filtrować potem bez utraty wydajności, choć nieznacznie zwiększone zużycie pamięci).

Ostateczna myśl.

Podejrzewam, że najnowocześniejsze komercyjne RDBMS oferują równoległość wątków w implementacji złączeń, więc to, co oferuje Hadoop, to paralelizm na poziomie maszynowym (dystrybucja). Z punktu widzenia projektowania, być może dobrym, prostym rozwiązaniem tego problemu jest umieszczenie danych w bazie danych, indeks na A i B (efektywne sortowanie danych) i użycie wewnętrznego sprzężenia SQL.

Answer 2

Jak o:

public static int[] intersectSortedArrays(int[] a, int[] b){ 
    int[] c = new int[Math.min(a.length, b.length)]; 
    int ai = 0, bi = 0, ci = 0; 
    while (ai < a.length && bi < b.length) { 
     if (a[ai] < b[bi]) { 
      ai++; 
     } else if (a[ai] > b[bi]) { 
      bi++; 
     } else { 
      if (ci == 0 || a[ai] != c[ci - 1]) { 
       c[ci++] = a[ai]; 
      } 
      ai++; bi++; 
     } 
    } 
    return Arrays.copyOfRange(c, 0, ci); 
} 

Koncepcyjnie jest podobny do Twojego, ale zawiera szereg uproszczeń.

Nie sądzę, że można poprawić złożoność czasu.

edytuj: Próbowałem tego kodu i przeszedł wszystkie twoje testy jednostkowe.

Answer 3

Jeśli korzystasz z tablic "Integer" (obiekt) i chcesz używać metod API Java, możesz sprawdzić poniższy kod. Zauważ, że poniższy kod prawdopodobnie ma większą złożoność (ponieważ używa pewnej logiki konwersji z jednej bazy danych do innej) i zużycie pamięci (z powodu używania obiektów) niż metoda pierwotna, jak podano powyżej.Właśnie spróbowałem (wzrusza):

public class MergeCollections { 
    public static void main(String[] args) { 
     Integer[] intArray1 = new Integer[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 
     Integer[] intArray2 = new Integer[] {2, 3, 5, 7, 8, 11, 13}; 

     Set<Integer> intSet1 = new TreeSet<Integer>(); 
     intSet1.addAll(Arrays.asList(intArray1)); 
     intSet1.addAll(Arrays.asList(intArray2)); 
     System.out.println(intSet1); 
    } 
} 

a wyjście:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13] 

także sprawdzić ten link: Algolist - Algo to merge sorted arrays

EDIT: Zmieniono HashSet do TreeSet

EDYCJA 2: Teraz że pytanie jest edytowany i jasne, Dodaję proste rozwiązanie, aby znaleźć punkt przecięcia:

public class Intersection { 
    public static void main(String[] args) { 
     Integer[] intArray1 = new Integer[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 
     Integer[] intArray2 = new Integer[] {2, 3, 5, 7, 8, 11, 13}; 

     List<Integer> list1 = Arrays.asList(intArray1); 
     Set<Integer> commonSet = new TreeSet<Integer>(); 
     for(Integer i: intArray2) { 
      if(list1.contains(i)) { 
       commonSet.add(i); 
      } 
     } 

     System.out.println(commonSet); 
    } 
} 

Answer 4

ja nie wiem, czy to jest dobry pomysł, aby rozwiązać ten problem w następujący sposób:

powiedzenia

A,B are 1 based arrays 
    A.length=m 
    B.length=n 

1) init, tablicę, C, mIN (m, n) długość

2) skupiają się tylko na części wspólnej sprawdzając pierwszy i ostatni element. tutaj można zastosować wyszukiwanie binarne. zrób przykład, aby zapisać kilka słów:

A[11,13,15,18,20,28,29,80,90,100.........300,400] 
    ^          ^
B[3,4,5,6,7.8.9.10.12,14,16,18,20,..400.....9999] 
        ^   ^


then we need only focus on 

    A[start=1](11)-A[end=m](400) 
    and 
    B[start=9](12)-B[end](400) 

3). porównaj zakres zakresu(end-start) obu tablic. biorąc pod tablicę z mniejszą zakresie, powiedzmy A, dla każdego elementu A[i] od A[start] ~ A[end], czy przeszukiwanie binarne w B[start,end],

• przypadku stwierdzenia, umieścić element C, reset B.start do foundIdx + 1,

• inaczej B.start ustawiony jest najmniejszy element [j], przy czym B [j] jest większy niż [I], w celu zawężenia zakresu

4) CO ntinue 3) do momentu przetworzenia wszystkich elementów w A [początek, koniec].

• po kroku 1, możemy znaleźć przypadek, jeśli nie ma skrzyżowania między dwiema tablicami .
• wykonując wyszukiwanie binarne w kroku 3, porównujemy A [i] z A [i-1], jeśli samo, pomiń A [i]. w celu zachowania elementów w C są unikalne.

w ten sposób, gorszy przypadek będzie lg (n!), Jeśli (A i B są takie same)? niepewny.

Śr. Skrzynka?

Answer 5

Oto poprawa pamięci:

Byłoby lepiej, aby zapisać swoje wyniki (c) w dynamicznej strukturze, jak połączonej listy i utworzyć tablicę po skończysz znalezienie elementów przecinających (dokładnie tak, jak robisz z tablicą r). Ta technika byłaby szczególnie dobra, gdybyś miał bardzo duże tablice dla A i B i spodziewałbyś się, że wspólne elementy będą nieliczne w porównaniu (po co szukać ogromnej porcji ciągłej pamięci, gdy potrzebujesz tylko małej ilości?).

EDYCJA: jeszcze jedna rzecz, którą chciałbym zmienić, a to może być trochę głupio wybredne, jest to, że unikałbym używania niezwiązanych pętli, gdy najgorsza liczba iteracji jest znana przed ręką.

Answer 6

Używanie arraylist do przechowywania wyników.

public ArrayList<Integer> arrayIntersection(int [] a, int[] b) 
{ 
    int len_a=a.length; 
    int len_b=b.length; 
    int i=0; 
    int j=0; 
    ArrayList<Integer> alist=new ArrayList(); 

    while(i<len_a && j<len_b) 
    { 
     if(a[i]<b[j]) 
      i++; 
     else if(a[i]>b[j]) 
      j++; 
     else if(a[i]==b[j]) 
     { 
      alist.add(a[i]); 
      i++; 
      j++; 

     } 
    } 

    return alist;  
    }