Skuteczne wyszukiwanie liczby mniejszych elementów dla każdego elementu w tablicy

Utknąłem na tym problemie:

Biorąc pod uwagę tablicę $A$ z pierwszego $n$ liczby naturalne losowo permutowane, tablica $B$ jest zbudowany tak, że $B(k)$ jest liczbą elementów od $A(1)$ do $A(k-1)$ które są mniejsze niż $A(k)$.

i) Biorąc pod uwagę $A$ czy możesz znaleźć $B$ w $O(n)$czas?
ii) Biorąc pod uwagę$B$ czy możesz znaleźć $A$ w $O(n)$ czas?

Tutaj, $B(1) = 0$. Konkretny przykład:

$$\begin{vmatrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & 4 & 4 \\ \end{vmatrix}$$

Czy ktoś może mi pomóc? Dzięki.

Naiwny algorytm ustalania $B$ od $A$:

Dla $k=1,\dots,n$, określ wartość $B(k)$ przez porównanie każdego z nich $A(i)$ do $A(k)$ dla $i=1,\dots,k$ i licząc tych, którzy spełniają $A(i)<A(k)$.

Ten algorytm się porównuje $A(1)$ dla wszystkich innych ($n-1$ czasy), $A(2)$ do $n-2$ inne itp., więc łączna liczba porównań wynosi $\frac{(n-1)(n-2)}{2}$. Ale to nie najlepsze, co możemy zrobić. Na przykład patrząc$B(n)$, nie musimy dokonywać żadnych porównań! $B(n)=A(n)-1$ponieważ to pierwszy $n$ liczby naturalne i jest gwarantowane (niezależnie od permutacji), że $n-1$będą tam niższe liczby naturalne. Co powiesz na$B(n-1)$? Zamiast sprawdzać$A(1)$ przez $A(n-2)$, moglibyśmy po prostu sprawdzić $A(n)$. To jest:

Dla $k=1, \dots,\frac{n}{2}$, użyj powyższego algorytmu; dla $k=\frac{n}{2},\dots,n$ użyj algorytmu odwrotnego: ustal $B(k)$ ustawiając go początkowo na $A(n)-1$ a następnie odejmowanie $1$ dla każdego wpisu $A(i)$ dla $i=k+1,\dots,n$ to mniej niż $A(k)$.

To zajmie $2\times\frac{(\frac{n}{2}-1) (\frac{n}{2}-2)}{2}=\frac{(n-2)(n-4)}{4}$ kroki, które są nadal $O(n^2)$. Zauważ też, że przy konstruowaniu$A$ od $B$, gdyby $B(n)=A(n)-1$ następnie $A(n)=B(n)+1$.

Ale teraz więcej finezji. Jeśli otrzymamy dodatkowe miejsce lub sortujemy w miejscu, możemy sortować liczby, porównując je. Na przykład:

$$\begin{vmatrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ S & 9 & 8 & 7 & 4 & 3 & 2 & 1 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & & \\ \end{vmatrix}$$

Zamiast sprawdzać je wszystkie (lub sprawdzać je w kolejności), możemy użyć wyszukiwania binarnego, aby ustalić każde z nich $B(k)$. Jednak sortowanie wciąż wymaga czasu$O(n\log n)$.

Zamiast ustalania każdego z nich $B(k)$ pojedynczo, możemy patrzeć w przyszłość i przeglądać tylko każdy numer $A$ raz ! Ale użyjemy$n$ przestrzeń:

$$\begin{vmatrix} A & & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & & B \\ 8 & & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \color{red}{0} & 1 & & 0\\ 4 & & 0 & 0 & 0 & \color{red}{0} & 1 & 1 & 1 & 1 & 2 & & 0\\ 3 & & 0 & 0 & \color{red}{0} & 1 & 2 & 2 & 2 & 2 & 3 & & 0\\ 1 & & \color{red}{0} & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 4 & & 0\\ 7 & & 0 & 1 & 1 & 2 & 3 & 3 & \color{red}{3} & 4 & 5 & & 3\\ 2 & & 0 & \color{red}{1} & 2 & 3 & 4 & 4 & 4 & 5 & 6 & & 1\\ 9 & & 0 & 1 & 2 & 3 & 4 & 4 & 4 & 5 & \color{red}{6} & & 6\\ 6 & & 0 & 1 & 2 & 3 & 4 & \color{red}{4} & 5 & 6 & 7 & & 4\\ 5 & & 0 & 1 & 2 & 3 & \color{red}{4} & 5 & 6 & 7 & 8 & & 4\\ \end{vmatrix}$$

Możemy zaoszczędzić jeszcze więcej czasu, nie aktualizując tych, które zostały już określone (to znaczy, nie ma sensu aktualizować $8$ po pierwszym kroku), ale w najgorszym przypadku nadal musimy dokonać aktualizacji $\frac{(n)(n+2)}{2}$ czasy

zarówno I, jak i II można rozwiązać za pomocą #next_greater_element, który tu wyjaśniłem . ale jest to trochę trudniejsze niż sam problem, ale przed rozwiązaniem musisz nauczyć się kolejnego większego elementu:

1. rozważmy, że mamy wektor dla każdego elementu $A$ Nazwij to $S_i$ dla elementu $i$. teraz uruchom kolejny większy algorytm, zaczynając od prawej do lewej, ale z wyjątkiem elementu ustawiającego$i$ w $A$ jego następny większy indeks elementów, wciśnij $S_i$ elementy, które $i$ jest ich kolejnym większym elementem. następnie iteruj po tablicy od lewej do prawej, a następnie $B[i]=\sum_{j=0}^x (S_i[j]+1)$ gdzie $x$ to rozmiar wektora $S_i$.i jej $\Theta(n)$ ponieważ każdy kolejny większy algorytm jest $\Theta(n)$ a także iteracja $\Theta(n)$

druga część jest również podobna, zauważając, że możemy uzyskać wartość najbardziej odpowiedniego elementu $O(1)$ EDYCJA: moje rozwiązanie jest złe, wydaje się, że nie ma żadnego$o(n)$ rozwiązanie