Witam,
Mam problem z pewną tablicą liczb.
Otóż mam liczby w pliku, które mogą się powtarzać. Sprawa wygląda następująco: potrzebuję wczytywać te liczby z pliku do tablicy ale cały myk polega na tym, że liczby które się powtarzają (niekoniecznie muszą być obok siebie w pliku) muszą być na sąsiednich indeksach w tablicy. Nie muszę mieć posortowanej całej tablicy rosnąco czy malejąco, a jedynie chciałbym aby te same liczby znalazły się na sąsiednich indeksach w tablicy. Czy jest na to jakiś sprytny sposób/algorytm/funkcja żeby nie trzeba było psuć złożoności całego programu sortowaniem?
Pozdrawiam
0
0
Hash mapa, implementacja istnieje chyba na każdym sensownym kompilatorze, w TR1 i c++0x nazywa się unordered_map. Zrób ją powiedzmy z inta na inta i zwiększaj pole odpowiadające wczytanej wartości o jeden. Zwykle osiągniesz zamortyzowaną złożoność O(1) dla pojedynczej operacji.
0
Użyj zliczania, dostaniesz swój efekt optymistycznie w O(n) dla małego zakresu liczb. Jak? W zależności od zakresu liczb:
- jeśli liczby są z małego zakresu [0..k] to tworzysz tablicę int[k];
- jeśli liczby są z dużego zakresu to tworzysz mapę map<int,int>
Wczytując liczby zliczasz ile takich liczb wczytano, tzn:
int liczby[k];
//pętelka wczytująca
int liczba;
cin>> liczba;
liczby[liczba]++;
W efekcie w tablicy masz przy każdej liczbie informacje o tym ile takich liczb wystąpiło. Następnie wystarczy do wynikowej tablicy wpisywać tyle liczb obok siebie ile powinno być w O(n)
Z mapą robimy to samo, ale niestety dostaniemy O(nlogn) bo <map> w C++ jest implementowana na drzewie a nie na tablicy hashującej (ale jak masz dostęp do takiej hashmapy to dostaniesz i tutaj O(n))
0
Pomysł ze zliczaniem już nawet udało mi się zrobić i działał ale problem polega na tym, że liczby są z bardzo dużego zakresu (long long int) więc nie mogę utworzyć tak rozległej tablicy. Nigdy nie używałem hash mapy. Program mogę pisać równie dobrze np. w javie ale czy tam hash mapa jest implementowana na tablicy? Nie ma jakiegoś innego sposobu?
0
W Javie masz dostępną HashMapę (masz też oczywiście TreeMap które jest odpowiednikiem <map> w c++) więc nie powinno być problemu. Ja nie mam pomysłu na inne rozwiązanie. To wydaje się najlepsze i najłatwiejsze, ot raptem z 15 linijek.
0
A jaka byłaby różnica w złożoności programu, gdyby przy każdym zczytywaniu liczby z pliku, leciał po tablicy do której wpisuje za każdym razem porównywał czy wyrazy z tablicy są równe sobie, a między wykorzystaniem hash mapy? Czy to nie będzie to samo?
0
Policz :P
Rozwiązanie z hashmapą ma złożoność średnią O(n)*O(1)+O(n) czyli w efekcie O(n).
Rozwiązanie które teraz podałeś ma średnią złożoność O(n^2) nie biorąc nawet pod uwagę konieczności "rozpychania" tablicy (którego w wersji z mapą nie ma, bo od razu wiadomo ile będzie elementów).