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.


Na PW przyjmuje tylko (ciekawe!) zlecenia. Masz problem? Pisz na forum, nie do mnie.

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.


Na PW przyjmuje tylko (ciekawe!) zlecenia. Masz problem? Pisz na forum, nie do mnie.

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