資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究連結串列中出現次數最多的字元
給定一個字元的單鏈表，我們的任務是列印在連結串列中出現次數最多的字元。如果多個字元具有相同的出現次數，則列印最後出現的字元。
單鏈表是一種線性資料結構，由節點組成。每個節點包含資料和指向下一個節點的指標，該指標包含下一個節點的記憶體地址，因為分配給每個節點的記憶體不是連續的。
示例
假設我們給定一個字元的連結串列，如下所示
示例 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。
我們將討論兩種方法。讓我們在下面的部分中檢視它們 -
方法 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){
// 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 迴圈遍歷每個小寫字元並維護計數。
更新於： 2023年5月17日
258 次檢視
廣告