Sortieren einer Warteschlange mit derselben queue
Ich habe diese Frage gestellt, und ich denke, es ist machbar, Aber ich habe eine harte Zeit kommen mit einem Algorithmus zu tun. Die Einschränkungen ist, dass Sie nicht verwenden können alle anderen Daten, die Struktur, noch erstellen Sie eine andere Warteschlange. Auch Sie nur verwenden können, enqueue, dequeue und peek (KEINE Priorität).
Danke für den Beitrag 🙂
- Ich wäre sehr überrascht, wenn Sie dies tun könnte. Allerdings denke ich, dass Sie brauchen, um ein wenig mehr spezifisch über welche Art von Arbeitsspeicher man verwenden darf. Ich nehme an, Sie sind nur erlaubt
O(1)
Speicher? - Es gibt keine Grenzen, weder in Zeit noch Raum Komplexität. Allerdings ist Es irgendwie impliziert, dass der Raum Komplexität wäre 1, es sei denn, es gibt eine rekursive Lösung, und die Zählung von StackFrames erstellt pro rekursiven Aufruf wird als Zugabe zu Speicherplatz-Komplexität.
- Tut
peek
nur den Kopf der Warteschlange, oder können Sie es verwenden, um den Wert von jeder position der Warteschlange? - Nur der Kopf der Warteschlange 🙂
- Stack-frames erstellt werden gezählt, sonst ist es eine sehr einfache Lösung.
- Können Sie bitte erläutern Sie mehr über die Lösung, die Sie im Sinn haben, gibt Es absolut keine Grenzen auf Komplexität
Du musst angemeldet sein, um einen Kommentar abzugeben.
Aufsteigend Sortieren, läuft in O(n^2) Zeit, in Platz O(1) (d.h. die Warteschlange ist O(n) Speicherplatz und zusätzliche Platzbedarf des Algorithmus ist O(1))
Erklärung:
Im wesentlichen, wir Durchlaufen der Warteschlange, n mal, jedes mal die Kosten iteration 2n.
Bei jeder iteration, gehen wir durch die gesamte Warteschlange und wählen Sie das minimum innerhalb der entsprechenden Anzahl von Gegenständen. Also zuerst die entsprechende Anzahl der Elemente n ist, da wir wollen das minimum von allen. Die nächste iteration wollen wir das minimum des ersten n-1 Elemente, und dann n-2 Elemente, etc. Da der Algorithmus stack diese Mindestanforderungen am Ende.
Einmal fanden wir das minimum, das wir brauchen, um die Iteration über den ganzen Stapel wieder in Ordnung zu schnappen Sie es und legen Sie es auf das Ende.
Die Grundidee hier ist, dass eine dequeue-gefolgt von einem enqueue-von dem gleichen element wird es uns ermöglichen, die zum Durchlaufen der Warteschlange und überprüfen Sie minimum - /maximum-unter Beibehaltung der Reihenfolge.
BubbleSort mit Hilfe des queue: