Wie speichere ich Daten im Array, um sie in O (n) Zeit sortiert zu drucken?

Question

In einem Spiel kann ein Benutzer 1 in jedem Zug zu einem Zähler von n Zähler hinzufügen (nummeriert 1,2,...,n). Für dieses Spiel, das er haben:

• Eine Funktion counter(i), die den Inhalt des Zählers i zurückgibt. in O(1) Zeit.

• Eine Funktion add(i), die den Zähler i erhöht. in O(1) Zeit.

• Eine Funktion print(), die die IDs sortiert nach dem Zählerinhalt in absteigender Reihenfolge druckt. in O(n) Zeit.

Wie ein solches Spiel in O(n) Platz zu implementieren?

Ich weiß, ich sollte die Zähler in Array halten, aber wie kann ich sie in O(n) Zeit sortiert drucken?

Answer 1

Sie können es mit einem Array und verknüpften Liste von verknüpften Listen lösen.

Das Array ist Mapping von Counter-ID zu dem Counter-Objekt, das ich später beschreiben werde.

Die Hauptliste ist eine Liste, in der jeder Knoten den Zählerbetrag darstellt. Jeder dieser Knoten hat eine Liste aller Gegenobjekte, die diese Menge haben, jeder hat einen Zeiger zurück auf den Knoten der Hauptliste (der Knoten, der den Betrag darstellt).

Wenn Sie Zähler i erhöhen, können Sie Ihr Objekt mit Ihrem Array in O(1) Zeit erhalten, als Sie den Zeiger verwenden können, den Sie den Knoten erreichen müssen, in dem sich dieses Objekt befindet, und um zu sehen, wie viel es darstellt . Jetzt können Sie das Counter-Objekt einfach loslösen und an die nächste Liste in O(1) Zeit anhängen (und eine solche Liste erstellen, wenn sie nicht existiert).

Der Druck ist einfach und dauert O(n) nur durch die Hauptliste zu durchlaufen.