Czy ciąg jest permutacją

Odpowiedz Nowy wątek
2011-08-22 14:59
0

Mam takie zadanie: sczytuję ciąg n liczb i mam sprawdzić, czy są one permutacją liczb od 1 do n. Pierwsza myśl to oczywiście najbardziej tępy brut w dwóch wariacjach:
a) robimy tablicę booleanów, w komórce o numerze równym aktualnie sczytywanej liczbie dajemy wartość true i na końcu robimy jeden przelot po tablicy - jeżeli od pierwszej do n-tej komórki nie było fałszu to jest to permutacja
b) tablicujemy te n liczb, sortujemy i robimy przelot po takiej tablicy sprawdzając, czy każda następna liczba to poprzednia+1
Szczerze jednak wątpię w optymalność takiego rozwiązania. Myślałem o sumie, ale ona nie gwarantuje istnienia permutacji, bo dla n=3 i {2,2,2} mamy "poprawną" sumę jak przy {1,3,2}, ale permutacji nie ma. Mógłby mnie ktoś oświecić?

Pozostało 580 znaków

2011-08-22 15:09
0

Zwykłe zliczanie da ci tutaj O(2n) i chyba nic szybszego nie znajdziesz. Suma byłaby dobra do stwierdzenia której z N liczba ci brakuje zakładając że są różne. Ale skoro nie wiesz czy są różne, to na nic się nie zda.

Pozostało 580 znaków

2011-08-22 15:14
0

Zwykłe zliczanie czyli brut w wersji b?

Pozostało 580 znaków

2011-08-22 15:32

Nie. To co opisałeś w wersji 1. Robisz tablicę w której zacznaczasz sobie tablica[x]=true; a potem sprawdzasz czy jest gdzieś false.

Pozostało 580 znaków

2011-08-22 15:36
0

OK, dzięki :)

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0