Watak yang paling kerap muncul dalam senarai terpaut

Kami diberi senarai aksara yang dipautkan secara tunggal, dan tugas kami ialah mencetak aksara yang paling kerap muncul dalam senarai terpaut. Jika berbilang aksara berlaku bilangan kali yang sama, kejadian terakhir aksara akan dicetak.

Senarai pautan tunggal ialah struktur data linear yang terdiri daripada nod. Setiap nod mengandungi data dan penunjuk ke nod seterusnya, yang mengandungi alamat memori nod seterusnya kerana memori yang diperuntukkan kepada setiap nod tidak bersebelahan.

Contoh

Andaikan kami telah diberikan senarai pautan watak

Contoh 1

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

Output: Watak yang paling biasa ialah c.

Penjelasan: Dalam senarai terpaut LL yang diberikan, a muncul sekali, b muncul sekali, dan c muncul 3 kali. Oleh itu, keluaran ialah c.

Contoh 2

Masukkan:

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

Output: Aksara berlaku terbesar ialah z.

Penjelasan: Dalam senarai terpaut LL yang diberikan, x muncul 2 kali, y muncul 2 kali, dan z muncul 2 kali. Semua kejadian adalah sama kerana z muncul terakhir, jadi output adalah z.

Di sini kita akan membincangkan dua kaedah. Mari lihat bahagian di bawah -

Kaedah 1: Kira kekerapan secara berulang

Idea kaedah ini ialah kita akan melintasi senarai terpaut dan mengira kekerapan setiap aksara, kemudian mencari aksara dengan kekerapan tertinggi, dan jika berbilang aksara mempunyai kekerapan yang sama, cetak aksara itu dan kembalikan aksara terakhir .

Contoh

#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;
}

Output

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

Kerumitan masa

: O(N*N), dengan N ialah saiz senarai terpaut.

Kerumitan ruang: O(1)

Kaedah 2: Gunakan tatasusunan mengira

Idea kaedah ini ialah kita akan mengekalkan tatasusunan kiraan di mana kita menyimpan kekerapan setiap aksara dan kemudian melelang melalui tatasusunan dan mencari aksara frekuensi tertinggi. Jika berbilang aksara mempunyai kekerapan yang sama, cetak aksara itu dan kemudian kembalikan aksara terakhir.

Contoh

#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;
}

Output

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

Kerumitan masa

O(N), dengan N ialah saiz senarai terpaut.

Kerumitan ruang: O(N), dengan N ialah saiz senarai terpaut.

Kesimpulan

Di sini kita membincangkan cara mencari aksara yang paling kerap dalam senarai terpaut. Untuk mencari kejadian maksimum aksara, kami membincangkan dua kaedah. Kaedah pertama menggunakan gelung sementara untuk setiap aksara senarai terpaut yang diberikan dan kaedah kedua menggunakan gelung for untuk setiap aksara huruf kecil dan mengekalkan kiraan.

Atas ialah kandungan terperinci Watak yang paling kerap muncul dalam senarai terpaut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!