Czy ciąg jest permutacją

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ć?

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.

0

Zwykłe zliczanie czyli brut w wersji b?

1

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.

0

OK, dzięki :)

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