Witam. Zastanawia mnie jakiej struktury danych użyć, by w najefektywniejszy sposób móc przestawiać elementy jakiegoś zbioru. Np. mam ciąg znaków "GHIJ" i chcę sobie np. przestawić "I" na początek, dzięki czemu uzyskam "IGHJ". Do czegoś takiego najlepszym rozwiązaniem będzie lista dwukierunkowa czy może da się to wykonać jakoś lepiej?
Struktury danych - jakiej użyć?
- Rejestracja: dni
- Ostatnio: dni
- Lokalizacja: XML Hills
0
Zadanie Litery?
Nie ma takiej implementacji listy, która w czasie O(1) pozwoli na operacje "dodaj", "usuń", "przesuń" oraz "odczytaj pozycję".
- Rejestracja: dni
- Ostatnio: dni
- Postów: 2518
0
lista jest dobra do usuwania i przestawiania, aczkolwiek odległości między literami odczytasz tylko w czasie liniowym, próbuj dalej :P da się to zrobić w O(n log n) kombinując trochę, a jak nic nie wymyślisz to postaraj się zrobić jak najszybsze O(n^2)