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
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 :)