Jak usunąć duplikaty z wektora C ++
„E” występuje trzy razy w różnych pozycjach. „A” występuje dwa razy w różnych pozycjach. „C” występuje dwa razy w różnych pozycjach. Więc „e”, „a” i „c” mają duplikaty. Każda z pozostałych postaci występuje raz.
Aby usunąć duplikaty w tym wektorze, oznacza usunięcie duplikatów „e”, „a” i „c” i pozwolić na pierwsze wystąpienie każdego znaku w pozycji. Wynik powinien być:
wektorIstnieją dwa główne sposoby usuwania duplikatów z wektora. Jednym ze sposobów jest droga bezpośrednia lub brutalna. W ten sposób pierwszy element jest sprawdzany w stosunku do reszty elementów, a każdy duplikat jest usuwany. Drugi element jest sprawdzany pod względem reszty pozostałych elementów po prawej stronie, usuwając duplikaty. Ta sama procedura odbywa się dla trzeciego elementu, a reszta elementów. W ten sposób zwykle trwa zbyt długo. Innym sposobem jest utrzymanie oryginalnego wektora i posiadanie posortowanej kopii. Usuń duplikaty z posortowanego wektora, wykonując kopię dowolnego zduplikowanego elementu, jako klucz na mapie. Wreszcie, skanuj przez oryginalny wektor od początku do końca za pomocą mapy do usuwania duplikatów.
Te dwa sposoby można określić odpowiednio jako metodą brutalną i metodą sortowania i składania. Ten artykuł ilustruje w obie strony. Nie zapomnij uwzględnić biblioteki wektorowej na początku programu.
Usuwanie elementu wektora
Element wektorowy jest usuwany za pomocą funkcji wymierania wektora. Składnia to:
ConstExpr Iterator Erase (pozycja Const_iterator);Argument jest iteratorem, który wskazuje na element, który ma zostać usunięty.
Usuwanie duplikatów za pomocą brutalnej siły
Przy takim podejściu pierwszy element jest porównywany z resztą elementów po prawej, jeden po drugiej i każdy duplikat jest wymazany. Drugi element, jeśli nie został usunięty, jest porównywany z resztą pozostałych elementów po prawej, jeden po drugiej, wymazujący duplikaty. Ta sama procedura odbywa się dla trzeciego elementu, a reszta elementów. To podejście zwykle trwa zbyt długo. Poniższy kod ilustruje go iteratorami:
vectorvtr = 'e', „g”, „i”, „e”, „a”, „e”, „c”, „a”, „c”;for (wektor :: iterator itei = vtr.zaczynać(); Itei
for (wektor :: iterator itej = itei+1; itej
vtr.usunąć (itej);
dla (int i = 0; i
Cout<
w nawiasach wewnętrznej pętli.
Usuwanie duplikatów przez sortowanie
Zauważ z powyższej metody, że istnieje wiele ponownego skanowania (ponowne czytanie i porównywanie) od dużej sekwencji, do małej sekwencji elementów jednego wektora. Jeśli cały wektor jest skanowany raz lub dwa lub trzy razy, prawdopodobnie oznaczałoby to mniej dostępu do elementów w porównaniu z powyższym podejściem. Cóż, całego wektora można nawet skanować cztery lub więcej razy, ale nie wiele razy. Nie musi to być wykonywane za pomocą tego samego wektora. Można to zrobić za pomocą kopii wektora.
Z drugim podejściem oryginalny wektor jest utrzymywany, a wykonana jest z niego posortowana kopia. Posortowany wektor jest odczytywany (zeskanowany), usuwając duplikat kolejnych elementów, które miały miejsce więcej niż raz. Jeden iterator na pętlę może to osiągnąć, od początku do końca posortowanego wektora, raz przez. Podczas gdy odczyt i pewne usuwanie ma miejsce, dla każdego elementu, który występuje więcej niż raz, kopia elementu jest wykonana na mapie, a odpowiednia wartość dla tego klucza jest podana wartość -1. Ta wartość -1 zostanie zmieniona na 1, aby wskazać duplikat. Każda wartość na mapie jest wskaźnikiem duplikatu jego klucza, który może wystąpić dwa lub więcej razy w oryginalnym wektorze.
Jeśli wymagany był posortowany wektor z usuniętymi duplikatami, wówczas zwracany jest posortowany wektor i wykonano pracę. Jeśli kolejność pierwszego wystąpienia elementów wektorowych musi zostać utrzymana, musi nastąpić następujący podprocedura (kontynuuj):
Od początku ponownie przeczytać oryginalny wektor. Podczas czytania, jeśli klucz nie występuje na mapie (mapa zwraca 0), zezwól na ten klucz w oryginalnym wektorze. Oznacza to, że klucz nie ma duplikatu. Jeśli na mapie występuje klucz oryginalnego wektora, oznacza to, że jest to pierwsze wystąpienie duplikatów dla tego elementu w wektorze. Wykonaj wartość wskaźnika dla klucza na mapie, 1. Ta wartość wskaźnika ma teraz wartość, 1. Kontynuuj czytanie reszty elementów w oryginalnym wektorze i sprawdzaj duplikat elementu za pomocą mapy. Jeśli znaleziono klucz, a wartość klucza mapy to 1, wówczas bieżący element jest duplikat. Usuń bieżący element. (Pamiętaj, że pierwsze wystąpienie zduplikowanego klucza obróciło odpowiednią wartość wskaźnika na mapie od -1 do 1.) Kontynuuj podawanie wartości 1 dla wskaźników klucza mapy, usuwając oryginalny bieżący element wektorowy, który ma już odpowiedni 1 na mapie z oryginalnego wektora; Do końca oryginalnego wektora. Powstały oryginalny wektor to wektor bez żadnego zduplikowanego elementu, a w kolejności z pierwszymi wydarzeniami.
Aby mapa kodowa w C ++, biblioteka mapy (UNORODED_MAP) musi być uwzględniona. Ponieważ zostanie użyta funkcja sort () w bibliotece algorytmu, biblioteka algorytmu również musi zostać włączona do programu. Kierowanie się do programu tego podejścia powinno być:
#włączać#włączać
#włączać
#włączać
za pomocą przestrzeni nazw Std;
Pierwszy segment kodu w głównej funkcji C ++ może być:
wektorwektor
Sort (vtr.początek (), vtr.koniec());
UNOPORDED_MAP
Pierwsza instrukcja określa oryginalny wektor. Drugie oświadczenie tworzy kopię oryginalnego wektora. Trzecie stwierdzenie sortuje skopiowany wektor. Czwarte stwierdzenie deklaruje mapę, bez inicjalizacji. Następnym segmentem kodu w głównej funkcji C ++ może być:
dla (wektor :: iterator iter = vtr.zaczynać(); iterif ( *iTer0 == *iTer1)
MP [*iTER1] = -1;
Iter-;
wektor :: iterator iter2 = vtr.usunąć (ITER1);
Ten segment kodu wymazuje duplikaty z posortowanego wektora skopiowanego. Robiąc to, tworzy wpisy mapy. Należy zauważyć, że w nawiasach za pętla iteracja dociera do elementu ostatniego, ale jednego (a nie ostatniego elementu). Wynika to z faktu, że obecne i następne elementy są zaangażowane w kod. Zwróć również uwagę, że gdy element ma zostać wymazany, iterator jest opóźniony (zmniejszany) o jeden krok.
Jeśli potrzebny jest posortowany wektor bez duplikatów, następujący kod wyświetliłby wynik:
dla (int i = 0; iCout<
Vtro.usunąć (itera);
Iter-;
if (mp [*iTer] == -1)
MP [*ITER] = 1;
Powodem wyboru -1 i 1, zamiast 0 i 1, jest to, że domyślna (nieobecna) wartość tej mapy wynosi 0. Unika to zamieszania z elementami, które w ogóle nie mają powielania. Zwykła w następujący sposób pętla może wydrukować ostateczny (zredukowany) oryginalny wektor:
dla (int i = 0; iCout<
Wyjście programu to:
A c e g iE g i a c
Pierwsza linia wyjścia jest sortowanym wejściem bez duplikatów. Druga linia to wejście w danej kolejności, z usuniętymi duplikatami.
Wniosek
Aby usunąć duplikaty z wektora C ++, można zastosować metodę brutalną. Ta metoda jest zwykle powolna. Czytelnikowi zaleca się użycie metody sortowania i kompozycji, która jest zwykle szybka, do pracy komercyjnej. Obie metody zostały wyjaśnione powyżej.