Takie zadanie pojawiło się na pierwszej liście z AiSD. Większość rozwiązań tego zadania dzieliło listę na pierwiastek z n bloków o równej długości. Sprawiało to wiele problemów w sytuacjach w których należało zwiększyć liczbę bloków (jak to zrobić, aby zmieścić się w czasie O(sqrt(n))?). Moje rozwiązanie opierało się na nieco innym pomyśle, dzięki czemu cała struktura danych staje się bardzo prosta i elegancka.
Podzielmy listę (dwukierunkową) na bloki. Pierwszy blok będzie miał jeden element; drugi blok dwa elementy, trzeci trzy... i tak dalej. Przy czym dopuszczamy, aby ostatni blok był niepełny. To będzie nasz niezmiennik. Taka lista będzie miała k dodatkowych wskaźników (na początki bloków) i każdy z bloków będzie miał rozmiar nie większy niż k. Liczba elementów na takiej liście będzie równa 1 + 2 + 3 + ... + k = k(k+1) / 2 = n. Zatem jak widzimy k jest rzędu O(sqrt(n)).
Wstawianie elementu el wykonujemy w czterech prostych krokach:
- Szukamy do którego bloku musi trafić element el (O(k) operacji).
- Szukamy w które miejsce ma trafić element i umieszczamy go w tym miejscu (O(k)).
- Przywracamy niezmiennik listy. Robimy to w ten sposób, że wskaźniki do wszystkich bloków znajdujących się na prawo od wstawionego elementu przesuwamy o jeden element w lewo (O(k) operacji).
- Jeśli ostatni blok przekroczy dozwolony rozmiar, to tworzymy nowy blok (O(1)).
Wstawienie elementu prezentuje poniższy rysunek.
Usuwanie elementu w sposób analogiczny.
2 komentarze:
afaik tam nie było nic o liście dwukierunkowej ;). przynajmniej w mojej grupie był z tym wałek.
Nie było też nic że nie może to być lista dwukierunkowa.
Jeśli już chcesz koniecznie aby to była lista jednokierunkowa to w zadaniu prosili tylko o operację wstawiania. Taką operację można wykonać za pomocą przedstawionej tu metody w odpowiednim czasie - wystarczy trzymać bloki w odwrotnej kolejności. To znaczy blok z jednym elementem trzymamy na końcu.
Prześlij komentarz