Das Zeichen, das in der verknüpften Liste am häufigsten vorkommt

Wir erhalten eine einfach verknüpfte Liste von Zeichen und unsere Aufgabe besteht darin, das Zeichen auszudrucken, das in der verknüpften Liste am häufigsten vorkommt. Wenn mehrere Zeichen gleich oft vorkommen, wird das letzte Vorkommen des Zeichens gedruckt.

Einfach verknüpfte Liste ist eine lineare Datenstruktur, die aus Knoten besteht. Jeder Knoten enthält Daten und einen Zeiger auf den nächsten Knoten, der die Speicheradresse des nächsten Knotens enthält, da der jedem Knoten zugewiesene Speicher nicht zusammenhängend ist.

Beispiel

Angenommen, wir haben eine Liste mit Charakterlinks erhalten

Beispiel 1

Eingabe: LL = a -> b -> c -> c -> c

Ausgabe: Das häufigste Zeichen ist c.

Erklärung: In der angegebenen verknüpften Liste LL erscheint a einmal, b einmal und c dreimal. Daher ist die Ausgabe c.

Beispiel 2

Geben Sie ein:

LL = x -> x -> y -> y -> z -> z

Ausgabe: Das größte vorkommende Zeichen ist z.

Erklärung: In der angegebenen verknüpften Liste LL erscheint x zweimal, y zweimal und z zweimal. Alle Vorkommen sind gleich, da z zuletzt erscheint, sodass die Ausgabe z ist.

Hier besprechen wir zwei Methoden. Werfen wir einen Blick auf die folgenden Teile -

Methode 1: Häufigkeit iterativ berechnen

Die Idee dieser Methode besteht darin, dass wir die verknüpfte Liste durchlaufen und die Häufigkeit jedes Zeichens berechnen, dann das Zeichen mit der höchsten Häufigkeit finden und, wenn mehrere Zeichen dieselbe Häufigkeit haben, dieses Zeichen drucken und das letzte Zeichen zurückgeben .

Beispiel

#include <iostream>
using namespace std;
// creating a class to have a structure for linked list nodes 
class Node{
   public:
   char data; // variable to store the characters
   Node* next = NULL; // variable to store the address of the next node     
   Node(char cur){
      data = cur;
   }
};
// function to print the elements of the linked list 
void printLL(Node* head){   
   // creating a temporary pointer 
   Node* temp = head;    
   while(temp != nullptr){
      cout<<temp->data<<" -> ";
      temp = temp->next;
   }
   cout<<"NULL"<<endl;
}
// function to find the max frequency 
void maxFreq(Node* head){
   // traversing over the linked list for each character 
   // starting from the first character to the last character     
   int ans = 0; // variable to store the maximum frequency 
   char char_ans;
   Node* temp_first = head; // variable to store the current first node     
   while(temp_first != nullptr){
      int cur = 0; // variable to store the frequency of the current character 
      Node* temp = temp_first;        
      while(temp != nullptr){
         if(temp->data == temp_first->data){
            cur++;
         }
         temp = temp->next;
      }
      if(ans < cur){
         ans = cur;
         char_ans = temp_first->data;
      }
      temp_first = temp_first->next;
   }
   cout<<"The last character in the given linked list is '"<<char_ans<<"' with the frequency of "<< ans<<endl;
}
// main function 
int main(){
   // defining the linked list 
   Node* head = new Node('a');
   head->next = new Node('b');
   head->next->next = new Node('b');
   head->next->next->next = new Node('c');
   head->next->next->next->next = new Node('d');
   head->next->next->next->next->next = new Node('d');
   head->next->next->next->next->next->next = new Node('d');  
   cout<<"The given linked list is: "<<endl;
   printLL(head);   
   maxFreq(head);
   return 0;
}

Ausgabe

The given linked list is: 
a -> b -> b -> c -> d -> d -> d -> NULL
The last character in the given linked list is 'd' with the frequency of 3

Zeitkomplexität

: O(N*N), wobei N die Größe der verknüpften Liste ist.

Raumkomplexität: O(1)

Methode 2: Zählarray verwenden

Die Idee dieser Methode besteht darin, dass wir ein Array von Zählungen verwalten, in dem wir die Häufigkeit jedes Zeichens speichern und dann das Array durchlaufen und das Zeichen mit der höchsten Häufigkeit finden. Wenn mehrere Zeichen dieselbe Häufigkeit haben, geben Sie dieses Zeichen aus und geben Sie dann das letzte Zeichen zurück.

Beispiel

#include <iostream>
using namespace std;
// creating a class to have a structure for linked list nodes 
class Node{
   public:
   char data; // variable to store the characters
   Node* next = NULL; // variable to store the address of the next node     
   Node(char cur){
      data = cur;
   }
};
// function to print the elements of the linked list 
void printLL(Node* head){    
   // creating a temporary pointer 
   Node* temp = head;    
   while(temp != nullptr){
      cout<<temp->data<<" -> ";
      temp = temp->next;
   }
   cout<<"NULL"<<endl;
}
// function to find the max frequency 
void maxFreq(Node* head){
   int ans = 0; // variable to store the maximum frequency 
   char char_ans;    
   // traversing over the linked list for each lowercase character 
   for(char i = 'a'; i<= 'z'; i++){
      Node* temp = head;
      int cur = 0; // variable to store the frequency of the current character 
      while(temp != nullptr){
         if(temp->data == i){
            cur++;
         }
         temp = temp->next;
      }
      if(ans <= cur){
         ans = cur;
         char_ans = i;
      }
   }     
   cout<<"The last character in the given linked list is '"<<char_ans<<"' with the frequency of "<< ans<<endl;
}
int main(){
   // defining the linked list 
   Node* head = new Node('a');
   head->next = new Node('b');
   head->next->next = new Node('b');
   head->next->next->next = new Node('c');
   head->next->next->next->next = new Node('e');
   head->next->next->next->next->next = new Node('d');
   head->next->next->next->next->next->next = new Node('d');  
   cout<<"The given linked list is: "<<endl;
   printLL(head);   
   maxFreq(head);
   return 0;
}

Ausgabe

The given linked list is: 
a -> b -> b -> c -> e -> d -> d -> NULL
The last character in the given linked list is 'd' with the frequency of 2

Zeitkomplexität

O(N), wobei N die Größe der verknüpften Liste ist.

Raumkomplexität: O(N), wobei N die Größe der verknüpften Liste ist.

Fazit

Hier besprechen wir, wie man die häufigsten Zeichen in einer verknüpften Liste findet. Um das maximale Vorkommen von Zeichen zu ermitteln, haben wir zwei Methoden besprochen. Die erste Methode verwendet eine while-Schleife für jedes Zeichen der angegebenen verknüpften Liste und die zweite Methode verwendet eine for-Schleife für jedes Kleinbuchstabenzeichen und behält die Anzahl bei.

Das obige ist der detaillierte Inhalt vonDas Zeichen, das in der verknüpften Liste am häufigsten vorkommt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!