我们给定了一个字符单链表,我们的任务是打印链表中出现次数最多的字符。如果多个字符出现的次数相同,则打印最后出现的字符。
单链表是一种由节点组成的线性数据结构。每个节点都包含数据和指向下一个节点的指针,该指针包含下一个节点的内存地址,因为分配给每个节点的内存不是连续的。
假设我们已经给出了一个字符链接列表
输入:LL = a -> b -> c -> c -> c
输出:最多出现的字符是 c。
解释:在给定的链表 LL 中,a 出现 1 次,b 出现 1 次,c 出现 3 次。因此,输出为c。
输入:
LL = x -> x -> y -> y -> z -> z
输出:最大出现的字符是 z。
解释:在给定的链表LL中,x出现2次,y出现2次,z出现2次。所有的出现次数都相同,因为 z 出现在最后,因此输出是 z。
在这里我们将讨论两种方法。让我们看看下面的部分 -
这种方法的思想是,我们将遍历链表并计算每个字符的频率,然后找出频率最大的字符,如果多个字符具有相同的频率,则打印该字符返回最后一个字符。
#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),其中N是链表的大小。
空间复杂度:O(1)
这种方法的想法是,我们将维护计数数组,在其中存储每个字符的频率,然后遍历该数组并找到频率最高的字符。如果多个字符具有相同的频率,则打印该字符,然后返回最后一个字符。
#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),其中N是链表的大小。
空间复杂度:O(N),其中 N 是链表的大小。
这里我们讨论了如何找到链表中出现最多的字符。为了找到最大出现的字符,我们讨论了两种方法。第一种方法对给定链表的每个字符使用 while 循环,第二种方法对每个小写字符使用 for 循环并维护计数。
以上是链表中出现次数最多的字符的详细内容。更多信息请关注PHP中文网其他相关文章!