Nous recevons une liste de caractères chaînés, et notre tâche est d'imprimer le caractère qui apparaît le plus fréquemment dans la liste chaînée. Si plusieurs caractères apparaissent le même nombre de fois, la dernière occurrence du caractère est imprimée.
Une liste chaînée unique est une structure de données linéaire composée de nœuds. Chaque nœud contient des données et un pointeur vers le nœud suivant, qui contient l'adresse mémoire du nœud suivant car la mémoire allouée à chaque nœud n'est pas contiguë.
Supposons que nous ayons reçu une liste de liens de personnages
Entrée : LL = a -> b -> c -> c -> c
Sortie : le caractère le plus courant est c.
Explication : Dans la liste chaînée donnée LL, a apparaît une fois, b apparaît une fois et c apparaît 3 fois. Par conséquent, la sortie est c.
Entrez :
LL = x -> x -> y -> y -> z -> z
Sortie : le plus grand caractère présent est z.
Explication : Dans la liste chaînée donnée LL, x apparaît 2 fois, y apparaît 2 fois et z apparaît 2 fois. Toutes les occurrences sont identiques car z apparaît en dernier, donc la sortie est z.
Ici, nous discuterons de deux méthodes. Jetons un coup d'œil aux parties ci-dessous -
L'idée de cette méthode est que nous allons parcourir la liste chaînée et calculer la fréquence de chaque caractère, puis trouver le caractère avec la fréquence la plus élevée, et si plusieurs caractères ont la même fréquence, imprimer ce caractère et renvoyer le dernier caractère .
#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; }
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
: O(N*N), où N est la taille de la liste chaînée.
Complexité spatiale : O(1)
L'idée de cette approche est que nous maintiendrons un tableau de décomptes dans lequel nous stockerons la fréquence de chaque caractère, puis parcourrons le tableau et trouverons le caractère de fréquence la plus élevée. Si plusieurs caractères ont la même fréquence, imprimez ce caractère puis renvoyez le dernier caractère.
#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; }
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
O(N), où N est la taille de la liste chaînée.
Complexité spatiale : O(N), où N est la taille de la liste chaînée.
Nous discutons ici de la façon de trouver les caractères les plus fréquents dans une liste chaînée. Pour trouver l’occurrence maximale de caractères, nous avons discuté de deux méthodes. La première méthode utilise une boucle while pour chaque caractère de la liste chaînée donnée et la deuxième méthode utilise une boucle for pour chaque caractère minuscule et maintient le décompte.
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!