Dla prostoty można założyć, że containerem jest zwykła tablica, np. w takiej formie:
int arr[5] = {1, 3, 2, 3, 4};
Pytania dwa:
1. Czy może jest jakieś gotowe rozwiązanie dzięki któremu mógłbym sprawdzić czy występują w tablicy duplikaty?
Wiem, że mogę najpierw skorzystać z std::sort
, a później z std::unique
, ale szukam czegoś bez sortowania. Alternatywnie mógłbym zduplikować tę tablicę i operować na duplikacie - dzięki temu pierwotna tablica by się nie zmieniła. Ale nadal byłoby to sortowanie, i na dodatek zajmowanie dodatkowej pamięci. Nie ma jakiejś gotowej metody dla nieposortowanej tablicy? To co ta metoda robi pod spodem już mniej mnie interesuje.
2. W sytuacji gdy nie chcę korzystać z gotowca, jak to zrobić optymalnie? Mógłbym to łatwo sprawdzić zagnieżdżonym forem w forze. Co najlepsze w tym to to, że bez sortowania, ale to nadal chyba O(n^2). Może ktoś jakiś efektywniejszy pseudokod chciałby podpowiedzieć? :)