Ograniczenia:

O (1) przestrzeńNa czas

To nie jest pytanie domowe, ale ciekawe pytanie, na które natrafiłem.

Oto kilka rozwiązań, które mogłem wymyślić, ale nic, co mogłoby to zrobić w danych ograniczeniach.

Metoda 1

* Z pamięcią O (n) *

Rekurencyjnie podziel tablicę na dwie części. (kontynuuj dzielenie aż do rozmiaru <= 2 dla każdego problemu sub)Sortuje każdy problem sub z tablicą jako pierwszą i liczbami na końcu.Scal tablice problemów podrzędnych

Metoda 2

W czasie O (n log n)

Posortuj porządek Lexicographical oparty na tablicy, aby stał się 1234abcdOdwróć obie połowy tablicy 4321dcbaOdwróć cały łańcuch abcd1234

Metoda 3

Jeśli zdefiniowano zakres liczb

Również jeśli przypadek był taki, że liczby są w określonym zakresie, mogę zainicjować ścieżkę int powiedzieć = 0; I ustaw odpowiedni bit, gdy natrafię na liczbę w tablicy np. (1 << a [2]). 1. Zamień alfabety na pierwszą połowę tablicy 2. Oznacz liczby w zmiennej ścieżki 3. później użyj ścieżki, aby wypełnić drugą połowę tablicy.

Metoda 4 Możemy użyć metody 3 z HashMap, jeśli chcemy usunąć ograniczenie zakresu liczb całkowitych, ale wtedy będzie potrzebować więcej pamięci.

Nie można wymyślić lepszego sposobu rozwiązania ogólnego problemu w czasie O (1) i przestrzeni O (n).

Ogólny problem dotyczy:

Biorąc pod uwagę sekwencję x1y1x2y2x3y3 .... xnyn gdzie x1, x2 są alfabetami x1 <x2 <.... <xn i y1y2 ... yn są liczbami całkowitymi. y1 <y2 <.... <yn Ustaw wyjście jako x1x2 ... xny1y2 ... yn

Jakieś sugestie ?