Algorytm znalezienia jeśli dwa zestawy przecinają

Załóżmy, że dwie matryce:Algorytm znalezienia jeśli dwa zestawy przecinają

Int Arraya [] = {5, 17, 150, 230, 285};

int ArrayB [] = {7, 11, 57, 110, 230, 250};

Obie tablice są posortowane i mogą mieć dowolny rozmiar. Szukam skutecznego algorytmu, który sprawdzi, czy tablice zawierają między sobą zduplikowane elementy. Chcę tylko odpowiedzi prawdziwej/fałszywej, nie obchodzi mnie, który element jest udostępniony, ani ile.

Naiwne rozwiązanie polega na przechodzeniu między poszczególnymi elementami ArrayA i wykonaniu w ArrayB binary search. Wierzę, że ta złożoność to O (m * log n).

Ponieważ obie tablice są posortowane, wydaje się, że powinien być skuteczniejszy algorytm.

Chciałbym również ogólne rozwiązanie, które nie zakłada, że tablice przechowują liczby (to znaczy, że rozwiązanie powinno również działać dla łańcuchów). Jednak operatory porównania są dobrze zdefiniowane i obie tablice są sortowane od najmniejszej do największej.

Źródło

2008-10-29 Imbue

Wystarczy marginesie, mówimy, że złożoność rozwiązania opisanego tu już jest O (m * log n), gdzie m i n są rozmiarami dwóch tablic. –

Miałem przeczucie, że to coś takiego. Dzięki. – Imbue

Udawaj, że robisz mergesort, ale nie wysyłaj wyników w dowolnym miejscu. Jeśli dojdziesz do końca któregokolwiek ze źródeł, nie ma przecięcia. Za każdym razem, gdy porównujesz następny element każdego, jeśli są równe, znajduje się przecięcie.

Na przykład:

counterA = 0; 
counterB = 0; 
for(;;) { 
    if(counterA == ArrayA.length || counterB == ArrayB.length) 
     return false; 
    else if(ArrayA[counterA] == ArrayB[counterB]) 
     return true; 
    else if(ArrayA[counterA] < ArrayB[counterB]) 
     counterA++; 
    else if(ArrayA[counterA] > ArrayB[counterB]) 
     counterB++; 
    else 
     halt_and_catch_fire(); 
}

Źródło

2008-10-29 01:59:07 Glomek

W przypadku, gdy nie jest to oczywiste, rozwiązaniem jest O (n) – Frentos

Czy jest to O (m + n)? – Imbue

BTW, to będzie działać dobrze z iteratorami C++ dla ogólnego kodu. To sprawia, że myślę, że STL powinien już dostarczyć rozwiązanie ... – Imbue

Jeśli nie dbają o zużycie pamięci, można osiągnąć dobre wyniki za pomocą skrótu, czyli tworzyć hash z kluczami = wartości jednej tablicy i testy wartości drugiej tablicy przeciwko temu hashowi

Źródło

2008-10-29 01:59:30 aku

Skróć mniejszą z dwóch tablic, aby zapisać jak najwięcej pamięci. To rozwiązanie na pewno szybko się rozpali. –

Zgadzam się. W ten sposób SQL Server wykonuje sprzężenie hash ... –

To jest O (n + m), podobnie jak przyjęte rozwiązanie. – ephemient

Jeśli zakres wartości jest mały, można utworzyć tabelę odnośników dla jednego z nich (koszt czasu = O (N)), a następnie sprawdzić, czy bit jest ustawiony z drugiej listy (koszt czasu = NA)). Jeśli zakres jest duży, możesz zrobić coś podobnego za pomocą tabeli mieszającej.

Sztuczka z mergesort od Glomek to jeszcze lepszy pomysł.

Źródło

2008-10-29 02:02:57

Glomek jest na dobrej drodze, ale trochę pomazał nad algorytmem.

Rozpocznij od porównania ArrayA [0] do ArrayB [0]. jeśli są równi, gotowe. Jeśli ArrayA [0] jest mniejsze niż ArrayB [0], przejdź do ArrayA [1]. Jeśli ArrayA [0] jest większe niż ArrayB [0], przejdź do ArrayB [1].

Przechodzenie przez kolejne etapy, aż dojdziesz do końca jednej tablicy lub znajdziesz dopasowanie.

Źródło

2008-10-29 02:05:17

Jeśli używasz C# 3.0, dlaczego nie skorzystać tutaj z LINQ?

ArrayA.Intersect(ArrayB).Any()

Nie tylko ten rodzajowy (działa dla każdego porównywalnego rodzaju) wdrożenie pod maską jest bardzo wydajny (używa algorytmu mieszającego).

Źródło

2008-10-29 05:18:46 JaredPar

Odkąd ktoś zastanawiał się nad stl. Po wyjęciu z pudełka algorytm set_intersection mógłby zrobić więcej, niż chcesz: znalazłby wszystkie wspólne wartości.

#include <vector> 
    #include <algorithm> 
    #include <iterator> 
    using namespace std; 
// ...  
     int ArrayA[] = {5, 17, 150, 230, 285}; 
     int ArrayB[] = {7, 11, 57, 110, 230, 250}; 
     vector<int> intersection; 
     ThrowWhenWritten output_iterator; 
     set_intersection(ArrayA, ArrayA + sizeof(ArrayA)/sizeof(int), 
         ArrayB, ArrayB + sizeof(ArrayB)/sizeof(int), 
         back_insert_iterator<vector<int> >(intersection)); 

     return !intersection.empty();

ten przebiega O (m + n), ale nie wymaga przechowywania wszystkie duplikaty i nie kończy się, kiedy znajdzie pierwszy DUP.

Teraz, modyfikując kod z gnu implementation stl, możemy uzyskać dokładniej to, co chcesz.

template<typename InputIterator1, typename InputIterator2> 
bool 
has_intersection(InputIterator1 first1, InputIterator1 last1, 
      InputIterator2 first2, InputIterator2 last2) 
    { 
     while (first1 != last1 && first2 != last2) 
     { 
      if (*first1 < *first2) 
      ++first1; 
      else if (*first2 < *first1) 
      ++first2; 
      else 
      return true; 
     } 
     return false; 
}

Źródło

2008-10-29 20:08:27

Przyjemnie i prosto, choć nie użyłbym nazw, które skopiowałeś z GNU, implementacja STL może używać tych symboli, ale POD (Plain Old Developer) nie jest dozwolona (podwójne podkreślenia i podkreślenie pisane dużymi literami są rozwiązywane dla realizacja). – Motti

Dobra uwaga, dzięki. –

Jeśli jedna lista jest znacznie krótsza od drugiej, szukanie binarne jest drogą do zrobienia. Jeśli listy mają podobną długość i jesteś zadowolony z O (m + n), standardowe "scalanie" będzie działało. Istnieją bardziej zaawansowane algorytmy, które są bardziej elastyczne. Jeden papier Natknąłem w moich własnych poszukiwań jest:

http://www.cs.uwaterloo.ca/~ajsaling/papers/paper-spire.pdf

Źródło

2008-10-31 14:13:59

Algorytm znalezienia jeśli dwa zestawy przecinają

Odpowiedz

Powiązane problemy