Ersetzen Sie mithilfe von C++ jeden Knoten in einer verknüpften Liste durch die entsprechende Anzahl von Knoten

Angesichts einer verknüpften Liste müssen wir das Element finden, das größer als die rechte Seite des aktuellen Elements in der angegebenen verknüpften Liste ist. Die Anzahl dieser Elemente muss in den Wert des aktuellen Knotens eingesetzt werden.

Nehmen wir eine verknüpfte Liste mit den folgenden Zeichen und ersetzen Sie jeden Knoten durch seine Überschreitungsanzahl –

4 -> 6 -> 1 -> 4 -> 6 -> 8 -> 5 -> 8 -> 3

Beginnen Sie rückwärts und durchlaufen Sie die verknüpfte Liste (damit wir uns nicht um das aktuelle Element links kümmern müssen). Unsere Datenstruktur verfolgt das aktuelle Element in sortierter Reihenfolge. Ersetzt das aktuelle Element in der sortierten Datenstruktur durch die Gesamtzahl der darüber liegenden Elemente.

Durch die rekursive Methode wird die verknüpfte Liste rückwärts durchlaufen. Eine weitere Option ist PBDS. Mithilfe von PBDS können wir Elemente finden, die unbedingt kleiner als ein bestimmter Schlüssel sind. Wir können das aktuelle Element addieren und vom strikt kleineren Element subtrahieren.

PBDS erlaubt keine doppelten Elemente. Zum Zählen benötigen wir jedoch wiederholte Elemente. Um jeden Eintrag eindeutig zu machen, fügen wir ein Paar (erstes = Element, zweites = Index) in das PBDS ein. Um die Gesamtzahl der Elemente zu ermitteln, die dem aktuellen Element entsprechen, verwenden wir eine Hash-Map. Eine Hash-Map speichert die Anzahl des Vorkommens jedes Elements (grundlegende Ganzzahl-zu-Ganzzahl-Zuordnung).

Beispiel

Das Folgende ist ein C++-Programm, um jeden Knoten in einer verknüpften Liste durch seine transzendente Nummer zu ersetzen -

#include <iostream>
#include <unordered_map>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define oset tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>

using namespace std;
using namespace __gnu_pbds;

class Node {
   public:
   int value;
   Node * next;
   Node (int value) {
      this->value = value;
      next = NULL;
   }
};
void solve (Node * head, oset & os, unordered_map < int, int >&mp, int &count){
   if (head == NULL)
   return;
   solve (head->next, os, mp, count);
   count++;
   os.insert (
   {
      head->value, count}
   );
   mp[head->value]++;
   int numberOfElements = count - mp[head->value] - os.order_of_key ({ head->value, -1 });
   head->value = numberOfElements;
}
void printList (Node * head) {
   while (head) {
      cout << head->value << (head->next ? "->" : "");
      head = head->next;
   }
   cout << "\n";
}
int main () {
   Node * head = new Node (43);
   head->next = new Node (65);
   head->next->next = new Node (12);
   head->next->next->next = new Node (46);
   head->next->next->next->next = new Node (68);
   head->next->next->next->next->next = new Node (85);
   head->next->next->next->next->next->next = new Node (59);
   head->next->next->next->next->next->next->next = new Node (85);
   head->next->next->next->next->next->next->next->next = new Node (37);
   oset os;
   unordered_map < int, int >mp;
   int count = 0;
   printList (head);
   solve (head, os, mp, count);
   printList (head);
   return 0;
}

Ausgabe

43->65->12->46->68->85->59->85->30
6->3->6->4->2->0->1->0->0

Anleitung

Für das erste Element gilt also element = [65, 46, 68, 85, 59, 85], also 6

Zweites Element, Element = [68, 85, 85], also 3

Alle Elemente und so weiter

Fazit

Diese Frage erfordert ein gewisses Verständnis der Datenstruktur und Rekursion. Wir müssen Methoden entwerfen und dann auf der Grundlage von Beobachtungen und Wissen Datenstrukturen ableiten, die unseren Anforderungen entsprechen. Wenn Ihnen dieser Artikel gefallen hat, lesen Sie weiter und bleiben Sie auf dem Laufenden.

Das obige ist der detaillierte Inhalt vonErsetzen Sie mithilfe von C++ jeden Knoten in einer verknüpften Liste durch die entsprechende Anzahl von Knoten. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!