Widziałem to pytanie na Careercup.com:

Biorąc pod uwagę wysokości n osób stojących w linii oraz listę liczb odpowiadających każdej osobie (p), która podaje liczbę osób, które są wyższe niż p i stoją przed p. Na przykład,

Wysokość: 5 3 2 6 1 4

InFronts: 0 1 2 0 3 2

Oznacza, że ​​rzeczywiste rzeczywiste zamówienie to: 5 3 2 1 6 4

Pytanie dostaje dwie listy Heights i InFronts i powinno wygenerować kolejność w kolejce.

Moje rozwiązanie:

Można to rozwiązać, najpierw sortując listę w porządku malejącym. Oczywiście, aby posortować, musimy zdefiniować obiekt Osoba (z dwoma atrybutami wysokości i Przodu), a następnie posortować Osoby na podstawie ich wysokości. Następnie użyłbym dwóch stosów, głównego stosu i tymczasowego, aby zbudować zamówienie.

Zaczynając od najwyższego, umieść go na głównym stosie. Jeśli następna osoba miała wartość InFront większą niż osoba na szczycie stosu, oznacza to, że nowa osoba powinna zostać dodana przed osobą na górze. Dlatego musimy pop osoby z głównego stosu, wstawić nową osobę, a następnie zwrócić osoby wyskakujące w pierwszym kroku. Chciałbym użyć stosu temp, aby zachować kolejność wyskakujących osób. Ale ile powinno się wyskoczyć? Ponieważ lista jest posortowana, musimy dokładnie wyświetlić liczbę osób przed nową osobą, tj. Odpowiadającą InFront.

Myślę, że to rozwiązanie działa. Ale najgorszym porządkiem przypadku byłby O (n ^ 2) - kiedy umieszczenie osoby na miejscu wymaga wyrzucenia wszystkich poprzednich.

Czy są jakieś inne rozwiązania? ewentualnie w O (n)?