Rumah > Artikel > pembangunan bahagian belakang > 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.
Andaikan kami telah diberikan senarai pautan watak
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.
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 -
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 .
#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), dengan N ialah saiz senarai terpaut.
Kerumitan ruang: O(1)
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.
#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), dengan N ialah saiz senarai terpaut.
Kerumitan ruang: O(N), dengan N ialah saiz senarai terpaut.
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!