W dniu 2013-10-28 17:01, Piotr pisze:
> W dniu 28.10.2013 o 16:51 <d...@g...com> pisze:
>
>> Cześć
>> Czy istnieje jakiś sprawny algorytm, który pozwoliłby zastąpić taki
>> lub podobny ciąg liczb:
>> 1,2,3,4,6,7,8,14,15,16,190,191,192,300 w takie coś:
>> 1-4,6-8,14-16,190-192,300
>>
>> ??
>
> w kółko
> wczytaj liczbę
> jeśli jest o 1 większa od poprzedniej
> poszerz ostatni zakres
> w przeciwnym wypadku
> utwórz nowy zakres


Zakładając, że ciąg jest posortowany.

Jeśli nie jest, mamy O(n log(n))

Ale nie bójmy się, akademicka (akademikowa) teoretyczność*)
idzie z pomocą.

Weźmy strukturę/algorytm find-union.
Zbiory (te z f-u) wzbogaćmy informacją o najmniejszym i największym
elemencie (aktualizowana O(1)). Trzeba to

Teraz już prosto. Na początek koszyczek zbiorów pusty.

while wejście niepuste
odczytaj nową liczbę -> x
if (!(find(x)))
nowy_zbiór(x)
if (find(x-1)) union(x,x-1)
if (find(x+1)) union(x,x+1)

Na koniec, przechodząc wszystkie zbiory dostajemy, również
nieposortowany, zestaw przedziałów.

Złożoność O ( dziwna_funkcja(n) * n )

zaś dziwna funkcja (Ackermana) rośnie bardzo powoli,
wolniej niż logarytm iterowany (ile razy trzeba zlogarytmować
liczbę, by dostać <1).

*) obstawiam, że sortowanie i tak może wygrać dla ludzkich
zbiorów danych.



:)

pzdr
bartekltg