Powiel możliwe:
Determining if an unordered vector<T> has all unique elementsSprawdzanie duplikatów w wektorze
muszę sprawdzić wektor duplikatów. Jaki jest najlepszy sposób podejścia:
Biorę pierwszy element, porównuję go ze wszystkimi innymi elementami w wektorze. Następnie weź następny element i wykonaj to samo i tak dalej.
Czy jest to najlepszy sposób, aby to zrobić, czy istnieje skuteczniejszy sposób sprawdzania dups?
Użyj hash table, w którym wstawisz każdy element. Przed wstawieniem elementu sprawdź, czy już go tam masz. Jeśli tak, masz duplikat. To jest O(n)średnio, ale najgorszy przypadek jest tak samo zły jak twoja obecna metoda.
Alternatywnie możesz użyć set, aby zrobić to samo w najgorszym przypadku w O(n log n). Jest to tak dobre, jak rozwiązanie do sortowania, z tym, że nie zmienia kolejności elementów (zużywa więcej pamięci, chociaż tworzysz zestaw).
Innym sposobem jest skopiowanie wektora do innego wektora, posortowanie go i sprawdzenie sąsiednich elementów. Nie jestem pewien, czy jest to szybsze od ustawionego rozwiązania, ale myślę, że sortowanie dodaje mniej narzutów niż zrównoważone drzewa wyszukiwania, których używa zestaw, więc powinno być szybciej w praktyce.
Oczywiście, jeśli nie zależy Ci na zachowaniu oryginalnej kolejności elementów, posortuj początkowy wektor.
Nie całkiem "tak dobry" jak rozwiązanie do sortowania. Jest to ta sama kolejność runtime, ale stały współczynnik sortowania wektora, który gwarantuje, że jego elementy sąsiadują z pamięcią, będzie znacznie mniejszy niż algorytm używający zestawu. Nie byłbym zaskoczony, gdyby był dwa razy szybszy. +1 i tak. Myślę, że masz najlepszą odpowiedź. –
@A. Levy: prawda, wspominałem o innej metodzie. – IVlad
Sortowanie Radix może być nawet szybsze niż O (n log n). http://en.wikipedia.org/wiki/Radix_sort –
Sortowanie, a następnie porównywanie sąsiednich elementów jest drogą do zrobienia. Sortowanie wymaga porównań O (n log n), a następnie dodatkowego n-1 do porównania sąsiednich elementów.
Schemat w pytaniu wymagałby (n^2)/2 porównań.
Jeśli wektor jest kontenerów STL, rozwiązanie jest proste:
Na przykład:
std::sort (myvec.begin(), myvec.end());
std::unique (myvec.begin(), myvec.end());
Zauważ, że std :: unique nie usuwa duplikatów, ale przenosi je na koniec kontenera i zwraca iterę do pierwszego duplikatu. W zależności od sytuacji możesz użyć polecenia std :: remove, aby usunąć koniec kontenera, lub użyj polecenia std :: copy, aby skopiować tylko te, które nie są duplikatami do innego kontenera.
Aby wyjaśnić, duplikaty nie są przenoszone na koniec zakresu; są one po prostu usuwane z przodu zakresu. Wartości elementów po nowym końcu zwróconym przez 'std :: unique()' są nieokreślone. Jeśli chcesz tylko sprawdzić, czy zakres nie zawiera duplikatów, 'std :: adjacent_find()' jest bardziej wydajny niż użycie 'std :: unique()'. –
Masz rację. Std :: unique umieszcza najpierw wszystkie unikatowe elementy i nie określa, co dzieje się z resztą kontenera. Najważniejszą rzeczą jest jednak pamiętać, że powinieneś użyć zwróconego iteratora i nie zakładać, że twój kontener zawiera tylko unikatowe elementy. Musisz ręcznie oczyścić ogon pojemnika. – Patrick
Możesz również użyć binary_search.
Oto dwa dobre przykłady, które pomogą Ci:
Jeśli nie dbają o sporadyczne fałszywie dodatni, można użyć Bloom Filter wykryć prawdopodobne duplikaty w kolekcja. Jeśli nie można zaakceptować fałszywych alarmów, weź wartości, które zawiodły w filtrze i uruchom na nich drugie przejście wykrywania. Lista wartości nieudanych powinna być dość mała, chociaż trzeba będzie je sprawdzić pod kątem pełnych danych wejściowych.
Duplikat [określanie, czy nieuporządkowana wektor ma wszystkie unikalne elementy] (http://stackoverflow.com/questions/2769174/determining-if-an-unordered-vectort-has-all-unique-elements) –
Can modyfikujesz wektor? Jeśli nie, czy masz pamięć do przydzielenia kopii? – florin