鍊錶中出現次數最多的字符

我們給定了一個字元單鍊錶，我們的任務是列印鍊錶中出現次數最多的字元。如果多個字元出現的次數相同，則列印最後出現的字元。

單鍊錶是一種由節點組成的線性資料結構。每個節點都包含資料和指向下一個節點的指針，該指針包含下一個節點的記憶體位址，因為分配給每個節點的記憶體不是連續的。

範例

假設我們已經給了一個字元連結列表

範例 1

輸入：LL = a -> b -> c -> c -> c

輸出：最多出現的字元是 c。

解釋：在給定的鍊錶 LL 中，a 出現 1 次，b 出現 1 次，c 出現 3 次。因此，輸出為c。

範例 2

輸入：

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)

方法 2：使用計數數組

這種方法的想法是，我們將維護計數數組，在其中儲存每個字元的頻率，然後遍歷該數組並找到頻率最高的字元。如果多個字符具有相同的頻率，則列印該字符，然後返回最後一個字符。

範例

#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中文網其他相關文章！