Effizientes Ermitteln der Anzahl kleinerer Elemente für jedes Element in einem Array

Ich bin bei diesem Problem festgefahren:

Wenn ein Array der ersten zufällig permutierten natürlichen Zahlen gegeben ist, wird ein Array so konstruiert, dass die Anzahl der Elemente von bis die kleiner als . $A$ $n$ $B$ $B(k)$ $A(1)$ $A(k-1)$ $A(k)$

i) Kannst du bei gegebenem in Zeit finden? ii) Kannst du bei gegebenem in Zeit finden? $A$ $B$ $O(n)$
$B$ $A$ $O(n)$

Hier ist . Ein konkretes Beispiel: $B(1) = 0$

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

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

Kann mir jemand helfen? Vielen Dank.

algorithms arrays permutations verdammt
quelle

Ich fand dies: Berechnen von Permutationscodierungen, die -Algorithmen für diese Probleme liefern. Zumindest denke ich, dass es die gleichen Probleme sind.

O (n \log n)

$\mathcal O(n \log n)$

Realz Slaw

@Merbs bedeutet dieser Hinweis, den Sie gegeben haben, dass Sie eine Lösung haben?

AJed

@AJed, es bedeutet, dass ich einen Algorithmus habe, obwohl es für den einfachen Algorithmus ohne Leerzeichen und braucht, wenn wir Speicherplatz haben. Im Moment neige ich dazu, in weder nicht möglich zu sein, noch beide den gleichen Algorithmus zu verwenden.

O (n^{2})

$O(n^2)$

O (n \log n)

$O(n\log n)$

O (n)

$O(n)$

Merbs

@Merbs. Ich denke, Ihr Hinweis kann zum richtigen Weg führen. Ich habe auch eine Lösung (nach Ihrem Hinweis). Ich denke, es gibt einen Trick in der Analyse, der dazu führt, dass es zu . Ich denke, der Trick ist das Wissen, dass von 1: geht .

O (n)

$O(n)$

A

$A$

n

$n$

AJed

In diesem Artikel wird auch ein -Algorithmus angegeben. Sind Sie sicher, dass es dafür einen -Algorithmus gibt?

O (n \log n)

$\mathcal O(n \log n)$

O (n)

$\mathcal O(n)$

Realz Slaw

Antworten:

Der naive Algorithmus zur Bestimmung von aus : $B$ $A$

Bestimmen Sie für den Wert von indem Sie jedes mit für und diejenigen zählen, die erfüllen . $k=1,\dots,n$ $B(k)$ $A(i)$ $A(k)$ $i=1,\dots,k$ $A(i)<A(k)$

Dieser Algorithmus vergleicht mit allen anderen ( mal), mit anderen usw., sodass die Gesamtzahl der Vergleiche beträgt. . Aber das ist nicht das Beste, was wir tun können. Wenn wir zum Beispiel , müssen wir keine Vergleiche anstellen! da es sich um die ersten natürlichen Zahlen handelt und garantiert ist (unabhängig von der Permutation), dass die niedrigeren natürlichen Zahlen vorhanden sind. Was ist mit ? Anstatt bis prüfen, könnten wir auch prüfen . Das ist: $A(1)$ $n-1$ $A(2)$ $n-2$ $\frac{(n-1)(n-2)}{2}$ $B(n)$ $B(n)=A(n)-1$ $n$ $n-1$ $B(n-1)$ $A(1)$ $A(n-2)$ $A(n)$

Verwenden Sie für den obigen Algorithmus. Verwenden Sie für den umgekehrten Algorithmus: Bestimmen Sie indem Sie ihn zunächst auf und dann für jeden Eintrag für subtrahieren , das ist kleiner als . $k=1, \dots,\frac{n}{2}$ $k=\frac{n}{2},\dots,n$ $B(k)$ $A(n)-1$ $1$ $A(i)$ $i=k+1,\dots,n$ $A(k)$

Dies würde Schritte, was immer noch . Beachten Sie auch, dass bei der Konstruktion von aus , wenn ist, . $2\times\frac{(\frac{n}{2}-1) (\frac{n}{2}-2)}{2}=\frac{(n-2)(n-4)}{4}$ $O(n^2)$ $A$ $B$ $B(n)=A(n)-1$ $A(n)=B(n)+1$

Aber jetzt zu mehr Finesse. Wenn wir zusätzlichen Platz oder eine Sortierung an Ort und Stelle haben, können wir die Zahlen sortieren, während wir sie vergleichen. Zum Beispiel:

| \begin{matrix} 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{matrix} |

$\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}$

Anstatt alle zu überprüfen (oder sie in der richtigen Reihenfolge zu überprüfen), könnten wir die binäre Suche verwenden, um jedes zu bestimmen . Die Sortierung benötigt jedoch noch Zeit . $B(k)$ $O(n\log n)$

Merbs
quelle

Dies war nur meine erste Idee; obwohl mir klar ist, dass das Problem interessanter ist, als ich es ursprünglich anerkannt habe. Und ich hatte noch keine Gelegenheit, die Ergebnisse von Realz Slaw zu lesen, sodass der Algorithmus möglicherweise nicht funktioniert.

Merbs

Anstatt jedes einzeln zu bestimmen , können wir vorausschauend sein und jede Zahl in einmal durchgehen ! Aber wir werden Leerzeichen verwenden: $B(k)$ $A$ $n$

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

$\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}$

Wir könnten noch mehr Zeit sparen, indem wir die bereits ermittelten nicht aktualisieren (dh es macht keinen Sinn, nach dem ersten Schritt zu aktualisieren), aber im schlimmsten Fall müssen wir mal $8$ $\frac{(n)(n+2)}{2}$

Merbs
quelle

Sowohl I als auch II sind mit #next_greater_element lösbar, das ich hier erklärt habe . Aber es ist etwas schwieriger als nur das Problem, aber vor der Lösung müssen Sie das nächst größere Element lernen:

Nehmen wir an, wir haben einen Vektor für jedes Element von nennen es für Element . nun einmal den nächsten größeren Algorithmus von rechts nach links laufen , aber ausgehend außer Einstellelement in den nächsten größeren Elementindex eindrücken die Elemente , die ihre nächstes größer ist element.then iterieren über das Array links nach rechts und dann wobei die Größe des Vektors und seines da jeder der nächstgrößere Algorithmus und auch Iteration ist $A$ $S_i$ $i$ $i$ $A$ $S_i$ $i$ $B[i]=\sum_{j=0}^x (S_i[j]+1)$ $x$ $S_i$ $\Theta(n)$ $\Theta(n)$ $\Theta(n)$

Der zweite Teil ist ähnlich und stellt fest, dass wir den Wert des am besten geeigneten Elements in EDIT erhalten können: Meine Lösung ist falsch, es scheint, dass es keine -Lösung gibt $O(1)$ $o(n)$

Ali.Mollahoseini
quelle