链表中出现的最大字符数-yiteyi-C++库

给出一个字符的链表。任务是找到链表中出现最多的字符。如果有多个答案，请返回第一个最大出现字符。

null

例如：

Input  : g -> e -> e -> k -> sOutput : eInput  : a -> a -> b -> b -> c -> c -> d -> dOutput : d

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

方法1： 迭代计算字符串中每个字符的频率，并返回出现次数最多的字符。

C++

                         // C++ program to count the maximum                       
                         // occurring character in linked list                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         /* Link list node */                       
                         struct                                     Node {                       
                                                 char                                     data;                       
                                                 struct                                     Node *next;                       
                         };                       
           
                         char                                     maxChar(                                     struct                                     Node *head) {                       
                                                 struct                                     Node *p = head;                       
           
                                                 int                                     max = -1;                       
                                                 char                                     res;                       
           
                                                 while                                     (p != NULL) {                       
           
                                                 // counting the frequency of current element                       
                                                 // p->data                       
                                                 struct                                     Node *q = p->next;                       
                                                 int                                     count = 1;                       
                                                 while                                     (q != NULL) {                       
                                                 if                                     (p->data == q->data)                       
                                                 count++;                       
           
                                                 q = q->next;                       
                                                 }                       
           
                                                 // if current counting is greater than max                       
                                                 if                                     (max < count) {                       
                                                 res = p->data;                       
                                                 max = count;                       
                                                 }                       
           
                                                 p = p->next;                       
                                                 }                       
           
                                                 return                                     res;                       
                         }                       
           
                         /* Push a node to linked list. Note that                       
                                                 this function changes the head */                       
                         void                                     push(                                     struct                                     Node **head_ref,                                     char                                     new_data) {                       
                                                 struct                                     Node *new_node =                                     new                                     Node;                       
                                                 new_node->data = new_data;                       
                                                 new_node->next = (*head_ref);                       
                                                 (*head_ref) = new_node;                       
                         }                       
           
                         /* Driver program to test above function*/                       
                         int                                     main() {                       
                                                 /* Start with the empty list */                       
                                                 struct                                     Node *head = NULL;                       
                                                 char                                     str[] =                                     "skeegforskeeg"                                     ;                       
                                                 int                                     i;                       
           
                                                 // this will create a linked list of                       
                                                 // character "geeksforgeeks"                       
                                                 for                                     (i = 0; str[i] !=                                     ' '                                     ; i++)                       
                                                 push(&head, str[i]);                       
           
                                                 cout << maxChar(head);                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to count the                       
                         // maximum occurring character                       
                         // in linked list                       
                         import                                     java.util.*;                       
                         class                                     GFG{                       
           
                         // Link list node                       
                         static                                     class                                     Node                       
                         {                       
                                                 char                                     data;                       
                                                 Node next;                       
                         };                       
                                   
                         static                                     Node head_ref;                       
                                   
                         static                                     char                                     maxChar(Node head)                       
                         {                       
                                                 Node p = head;                       
                                                 int                                     max = -                                     1                                     ;                       
                                                 char                                     res =                                     '0'                                     ;                       
           
                                                 while                                     (p !=                                     null                                     )                       
                                                 {                       
                                                 // counting the frequency                       
                                                 // of current element                       
                                                 // p.data                       
                                                 Node q = p.next;                       
                                                 int                                     count =                                     1                                     ;                       
                                   
                                                 while                                     (q !=                                     null                                     )                       
                                                 {                       
                                                 if                                     (p.data == q.data)                       
                                                 count++;                       
           
                                                 q = q.next;                       
                                                 }                       
           
                                                 // if current counting                       
                                                 // is greater than max                       
                                                 if                                     (max < count)                       
                                                 {                       
                                                 res = p.data;                       
                                                 max = count;                       
                                                 }                       
           
                                                 p = p.next;                       
                                                 }                       
           
                                                 return                                     res;                       
                         }                       
           
                         // Push a node to linked list.                       
                         // Note that this function                       
                         // changes the head                       
                         static                                     void                                     push(                                     char                                     new_data)                       
                         {                       
                                                 Node new_node =                                     new                                     Node();                       
                                                 new_node.data = new_data;                       
                                                 new_node.next = head_ref;                       
                                                 head_ref = new_node;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 // Start with the empty list                       
                                                 head_ref =                                     null                                     ;                       
                                                 String str =                                     "skeegforskeeg"                                     ;                       
                                                 char                                     st[] = str.toCharArray();                       
                                                 int                                     i;                       
           
                                                 // this will create a linked                       
                                                 // list of character "geeksforgeeks"                       
                                                 for                                     (i =                                     0                                     ; i < st.length; i++)                       
                                                 push(st[i]);                       
           
                                                 System.out.print(maxChar(head_ref));                       
                         }                       
                         }                       
           
                         // This code is contributed by shikhasingrajput                       

Python3

                         # Python program to count the                       
                         # maximum occurring character                       
                         # in linked list                       
           
                         # Link list Node                       
                         class                                     Node:                       
                                                 def                                     __init__(                                     self                                     , data):                       
                                                 self                                     .data                                     =                                     data;                       
                                                 self                                     .                                     next                                     =                                     next                                     ;                       
           
                         head_ref                                     =                                     None                                     ;                       
           
                         def                                     maxChar(head):                       
                                                 p                                     =                                     head;                       
                                                 max                                     =                                     -                                     1                                     ;                       
                                                 res                                     =                                     '0'                                     ;                       
           
                                                 while                                     (p !                                     =                                     None                                     ):                       
                                                 # counting the frequency                       
                                                 # of current element                       
                                                 # p.data                       
                                                 q                                     =                                     p.                                     next                                     ;                       
                                                 count                                     =                                     1                                     ;                       
           
                                                 while                                     (q !                                     =                                     None                                     ):                       
                                                 if                                     (p.data                                     =                                     =                                     q.data):                       
                                                 count                                     +                                     =                                     1                                     ;                       
           
                                                 q                                     =                                     q.                                     next                                     ;                       
           
                                                 # if current counting                       
                                                 # is greater than max                       
                                                 if                                     (                                     max                                     < count):                       
                                                 res                                     =                                     p.data;                       
                                                 max                                     =                                     count;                       
           
                                                 p                                     =                                     p.                                     next                                     ;                       
           
                                                 return                                     res;                       
           
                         # Push a Node to linked list.                       
                         # Note that this function                       
                         # changes the head                       
                         def                                     push(new_data):                       
                                                 global                                     head_ref;                       
                                                 new_node                                     =                                     Node(                                     0                                     );                       
                                                 new_node.data                                     =                                     new_data;                       
                                                 new_node.                                     next                                     =                                     head_ref;                       
                                                 head_ref                                     =                                     new_node;                       
                                                 head_ref                                     =                                     new_node;                       
           
                         # Driver code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                   
                                                 # Start with the empty list                       
                                                 head_ref                                     =                                     None                                     ;                       
                                                 str                                     =                                     "skeegforskeeg"                                     ;                       
                                                 st                                     =                                     str                                     ;                       
                                                 i                                     =                                     0                                     ;                       
           
                                                 # this will create a linked                       
                                                 # list of character "geeksforgeeks"                       
                                                 for                                     i                                     in                                     range                                     (                                     len                                     (st)):                       
                                                 push(st[i]);                       
           
                                                 print                                     (maxChar(head_ref));                       
           
                         # This code is contributed by shikhasingrajput                       

C#

                         // C# program to count the                       
                         // maximum occurring character                       
                         // in linked list                       
                         using                                     System;                       
                         class                                     GFG                       
                         {                       
                                   
                         // Link list node                       
                         class                                     Node                       
                         {                       
                                                 public                                     char                                     data;                       
                                                 public                                     Node next;                       
                         };                       
                                   
                         static                                     Node head_ref;                       
                                   
                         static                                     char                                     maxChar(Node head)                       
                         {                       
                                                 Node p = head;                       
                                                 int                                     max = -1;                       
                                                 char                                     res =                                     '0'                                     ;                       
                                   
                                                 while                                     (p !=                                     null                                     )                       
                                                 {                       
                                   
                                                 // counting the frequency                       
                                                 // of current element                       
                                                 // p.data                       
                                                 Node q = p.next;                       
                                                 int                                     count = 1;                       
                                   
                                                 while                                     (q !=                                     null                                     )                       
                                                 {                       
                                                 if                                     (p.data == q.data)                       
                                                 count++;                       
                                                 q = q.next;                       
                                                 }                       
                                   
                                                 // if current counting                       
                                                 // is greater than max                       
                                                 if                                     (max < count)                       
                                                 {                       
                                                 res = p.data;                       
                                                 max = count;                       
                                                 }                       
                                   
                                                 p = p.next;                       
                                                 }                       
                                   
                                                 return                                     res;                       
                         }                       
                                   
                         // Push a node to linked list.                       
                         // Note that this function                       
                         // changes the head                       
                         static                                     void                                     push(                                     char                                     new_data)                       
                         {                       
                                                 Node new_node =                                     new                                     Node();                       
                                                 new_node.data = new_data;                       
                                                 new_node.next = head_ref;                       
                                                 head_ref = new_node;                       
                         }                       
                                   
                         // Driver code                       
                         public                                     static                                     void                                     Main(                                     string                                     [] args)                       
                         {                       
                                   
                                                 // Start with the empty list                       
                                                 head_ref =                                     null                                     ;                       
                                                 string                                     str =                                     "skeegforskeeg"                                     ;                       
                                                 char                                     []st = str.ToCharArray();                       
                                                 int                                     i;                       
                                   
                                                 // this will create a linked                       
                                                 // list of character "geeksforgeeks"                       
                                                 for                                     (i = 0; i < st.Length; i++)                       
                                                 push(st[i]);                       
                                   
                                                 Console.Write(maxChar(head_ref));                       
                         }                       
                         }                       
           
                         // This code is contributed by rutvik_56                       

Javascript

                         <script>                       
           
                         // Javascript program to count the                       
                         // maximum occurring character                       
                         // in linked list                       
                                   
                         // Link list node                       
                         class Node                       
                         {                       
                                                 constructor()                       
                                                 {                       
                                                 this                                     .data =                                     ''                                     ;                       
                                                 this                                     .next =                                     null                                     ;                       
                                                 }                       
                         };                       
                                   
                         var                                     head_ref =                                     null                                     ;                       
                                   
                         function                                     maxChar( head)                       
                         {                       
                                                 var                                     p = head;                       
                                                 var                                     max = -1;                       
                                                 var                                     res =                                     '0'                                     ;                       
                                   
                                                 while                                     (p !=                                     null                                     )                       
                                                 {                       
                                   
                                                 // counting the frequency                       
                                                 // of current element                       
                                                 // p.data                       
                                                 var                                     q = p.next;                       
                                                 var                                     count = 1;                       
                                   
                                                 while                                     (q !=                                     null                                     )                       
                                                 {                       
                                                 if                                     (p.data == q.data)                       
                                                 count++;                       
                                                 q = q.next;                       
                                                 }                       
                                   
                                                 // if current counting                       
                                                 // is greater than max                       
                                                 if                                     (max < count)                       
                                                 {                       
                                                 res = p.data;                       
                                                 max = count;                       
                                                 }                       
                                   
                                                 p = p.next;                       
                                                 }                       
                                   
                                                 return                                     res;                       
                         }                       
                                   
                         // Push a node to linked list.                       
                         // Note that this function                       
                         // changes the head                       
                         function                                     push(new_data)                       
                         {                       
                                                 var                                     new_node =                                     new                                     Node();                       
                                                 new_node.data = new_data;                       
                                                 new_node.next = head_ref;                       
                                                 head_ref = new_node;                       
                         }                       
                                   
                         // Driver code                       
                         // Start with the empty list                       
                         head_ref =                                     null                                     ;                       
                         var                                     str =                                     "skeegforskeeg"                                     ;                       
                         var                                     st = str.split(                                     ''                                     );                       
                         var                                     i;                       
           
                         // this will create a linked                       
                         // list of character "geeksforgeeks"                       
                         for                                     (i = 0; i < st.length; i++)                       
                                                 push(st[i]);                       
           
                         document.write(maxChar(head_ref));                       
           
                         </script>                       

输出：

时间复杂性： （N*N）

方法2：（使用计数数组） 创建计数数组并计数每个字符的频率，返回最大出现字符数。

C++

                         // C++ program to count the maximum                       
                         // occurring character in linked list                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         /* Link list node */                       
                         struct                                     Node {                       
                                                 char                                     data;                       
                                                 struct                                     Node *next;                       
                         };                       
           
                         char                                     maxChar(                                     struct                                     Node *head) {                       
                                                 struct                                     Node *p = head;                       
                                                 int                                     hash[256] = {0};                       
           
                                                 // Storing element's frequencies                       
                                                 // in a hash table.                       
                                                 while                                     (p != NULL) {                       
                                                 hash[p->data]++;                       
                                                 p = p->next;                       
                                                 }                       
           
                                                 p = head;                       
           
                                                 int                                     max = -1;                       
                                                 char                                     res;                       
           
                                                 // calculating the first maximum element                       
                                                 while                                     (p != NULL) {                       
                                                 if                                     (max < hash[p->data]) {                       
                                                 res = p->data;                       
                                                 max = hash[p->data];                       
                                                 }                       
                                                 p = p->next;                       
                                                 }                       
                                                 return                                     res;                       
                         }                       
           
                         /* Push a node to linked list. Note that                       
                                                 this function changes the head */                       
                         void                                     push(                                     struct                                     Node **head_ref,                                     char                                     new_data) {                       
                                                 struct                                     Node *new_node =                                     new                                     Node;                       
                                                 new_node->data = new_data;                       
                                                 new_node->next = (*head_ref);                       
                                                 (*head_ref) = new_node;                       
                         }                       
           
                         /* Driver program to test above function*/                       
                         int                                     main() {                       
                                                 struct                                     Node *head = NULL;                       
                                                 char                                     str[] =                                     "skeegforskeeg"                                     ;                       
                                                 for                                     (                                     int                                     i = 0; str[i] !=                                     ' '                                     ; i++)                       
                                                 push(&head, str[i]);                       
                                                 cout << maxChar(head);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to count the maximum                       
                         // occurring character in linked list                       
                         import                                     java.util.*;                       
           
                         class                                     GFG                       
                         {                       
           
                         /* Link list node */                       
                         static                                     class                                     Node                       
                         {                       
                                                 char                                     data;                       
                                                 Node next;                       
                         };                       
           
                         static                                     Node head;                       
                         static                                     char                                     maxChar(Node head)                       
                         {                       
                                                 Node p = head;                       
                                                 int                                     []hash =                                     new                                     int                                     [                                     256                                     ];                       
                                   
                                                 // Storing element's frequencies                       
                                                 // in a hash table.                       
                                                 while                                     (p !=                                     null                                     )                       
                                                 {                       
                                                 hash[p.data]++;                       
                                                 p = p.next;                       
                                                 }                       
                                   
                                                 p = head;                       
                                   
                                                 int                                     max = -                                     1                                     ;                       
                                                 char                                     res =                                     0                                     ;                       
                                   
                                                 // calculating the first maximum element                       
                                                 while                                     (p !=                                     null                                     )                       
                                                 {                       
                                                 if                                     (max < hash[p.data])                       
                                                 {                       
                                                 res = p.data;                       
                                                 max = hash[p.data];                       
                                                 }                       
                                                 p = p.next;                       
                                                 }                       
                                                 return                                     res;                       
                         }                       
                                   
                         /* Push a node to linked list. Note that                       
                         this function changes the head */                       
                         static                                     void                                     push(Node head_ref,                                     char                                     new_data)                       
                         {                       
                                                 Node new_node =                                     new                                     Node();                       
                                                 new_node.data = new_data;                       
                                                 new_node.next = head_ref;                       
                                                 head_ref = new_node;                       
                                                 head = head_ref;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 head =                                     null                                     ;                       
                                                 char                                     str[] =                                     "skeegforskeeg"                                     .toCharArray();                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < str.length; i++)                       
                                                 {                       
                                                 push(head, str[i]);                       
                                                 }                       
                                                 System.out.println(maxChar(head));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Rajput-Ji                       

Python3

                         # Python3 program to count the maximum                       
                         # occurring character in linked list                       
                                   
                         # Link list node                       
                         class                                     Node:                       
                                   
                                                 def                                     __init__(                                     self                                     ):                       
                                   
                                                 self                                     .data                                     =                                     ''                       
                                                 self                                     .                                     next                                     =                                     None                       
           
                         def                                     maxChar(head):                       
                                   
                                                 p                                     =                                     head                       
                                                 hash                                     =                                     [                                     0                                     for                                     i                                     in                                     range                                     (                                     256                                     )]                       
           
                                                 # Storing element's frequencies                       
                                                 # in a hash table.                       
                                                 while                                     (p !                                     =                                     None                                     ):                       
                                                 hash                                     [                                     ord                                     (p.data)]                                     +                                     =                                     1                       
                                                 p                                     =                                     p.                                     next                       
           
                                                 p                                     =                                     head                       
           
                                                 max                                     =                                     -                                     1                       
                                                 res                                     =                                     ''                       
           
                                                 # Calculating the first maximum element                       
                                                 while                                     (p !                                     =                                     None                                     ):                       
                                                 if                                     (                                     max                                     <                                     hash                                     [                                     ord                                     (p.data)]):                       
                                                 res                                     =                                     p.data                       
                                                 max                                     =                                     hash                                     [                                     ord                                     (p.data)]                       
                                   
                                                 p                                     =                                     p.                                     next                       
                                   
                                                 return                                     res                       
           
                         # Push a node to linked list. Note that                       
                         # this function changes the head                       
                         def                                     push(head_ref, new_data):                       
                                   
                                                 new_node                                     =                                     Node()                       
                                                 new_node.data                                     =                                     new_data                       
                                                 new_node.                                     next                                     =                                     (head_ref)                       
                                                 (head_ref)                                     =                                     new_node                       
                                                 return                                     head_ref                       
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                   
                                                 head                                     =                                     None                       
                                                 str                                     =                                     "skeegforskeeg"                       
                                   
                                                 for                                     i                                     in                                     range                                     (                                     len                                     (                                     str                                     )):                       
                                                 head                                     =                                     push(head,                                     str                                     [i])                       
                                   
                                                 print                                     (maxChar(head))                       
                                   
                         # This code is contributed by pratham76                       

C#

                         // C# program to count the maximum                       
                         // occurring character in linked list                       
                         using                                     System;                       
                                   
                         public                                     class                                     GFG                       
                         {                       
                                   
                         /* Link list node */                       
                         class                                     Node                       
                         {                       
                                                 public                                     char                                     data;                       
                                                 public                                     Node next;                       
                         };                       
                                   
                         static                                     Node head;                       
                         static                                     char                                     maxChar(Node head)                       
                         {                       
                                                 Node p = head;                       
                                                 int                                     []hash =                                     new                                     int                                     [256];                       
                                   
                                                 // Storing element's frequencies                       
                                                 // in a hash table.                       
                                                 while                                     (p !=                                     null                                     )                       
                                                 {                       
                                                 hash[p.data]++;                       
                                                 p = p.next;                       
                                                 }                       
                                   
                                                 p = head;                       
                                   
                                                 int                                     max = -1;                       
                                                 char                                     res=                                     'x0000'                                     ;                       
                                   
                                                 // calculating the first maximum element                       
                                                 while                                     (p !=                                     null                                     )                       
                                                 {                       
                                                 if                                     (max < hash[p.data])                       
                                                 {                       
                                                 res = p.data;                       
                                                 max = hash[p.data];                       
                                                 }                       
                                                 p = p.next;                       
                                                 }                       
                                                 return                                     res;                       
                         }                       
                                   
                         /* Push a node to linked list. Note that                       
                         this function changes the head */                       
                         static                                     void                                     push(Node head_ref,                                     char                                     new_data)                       
                         {                       
                                                 Node new_node =                                     new                                     Node();                       
                                                 new_node.data = new_data;                       
                                                 new_node.next = head_ref;                       
                                                 head_ref = new_node;                       
                                                 head = head_ref;                       
                         }                       
                                   
                         // Driver Code                       
                         public                                     static                                     void                                     Main(String[] args)                       
                         {                       
                                                 head =                                     null                                     ;                       
                                                 char                                     []str =                                     "skeegforskeeg"                                     .ToCharArray();                       
                                                 for                                     (                                     int                                     i = 0; i < str.Length; i++)                       
                                                 {                       
                                                 push(head, str[i]);                       
                                                 }                       
                                                 Console.WriteLine(maxChar(head));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by 29AjayKumar                       

Javascript

                         <script>                       
           
                         // JavaScript program to count the maximum                       
                         // occurring character in linked list                       
           
                         // Link list node                       
                         class Node                       
                         {                       
                                                 constructor()                       
                                                 {                       
                                                 this                                     .data = 0;                       
                                                 this                                     .next =                                     null                                     ;                       
                                                 }                       
                         }                       
           
                         var                                     head =                                     null                                     ;                       
                         function                                     maxChar(head)                       
                         {                       
                                                 var                                     p = head;                       
                                                 var                                     hash =                                     new                                     Array(256).fill(0);                       
                                   
                                                 // Storing element's frequencies                       
                                                 // in a hash table.                       
                                                 while                                     (p !=                                     null                                     )                       
                                                 {                       
                                                 hash[p.data.charCodeAt(0)]++;                       
                                                 p = p.next;                       
                                                 }                       
                                   
                                                 p = head;                       
                                   
                                                 var                                     max = -1;                       
                                                 var                                     res =                                     ""                                     ;                       
                                   
                                                 // Calculating the first maximum element                       
                                                 while                                     (p !=                                     null                                     )                       
                                                 {                       
                                                 if                                     (max < hash[p.data.charCodeAt(0)])                       
                                                 {                       
                                                 res = p.data;                       
                                                 max = hash[p.data.charCodeAt(0)];                       
                                                 }                       
                                                 p = p.next;                       
                                                 }                       
                                                 return                                     res;                       
                         }                       
           
                         // Push a node to linked list. Note that                       
                         // this function changes the head                       
                         function                                     push(head_ref, new_data)                       
                         {                       
                                                 var                                     new_node =                                     new                                     Node();                       
                                                 new_node.data = new_data;                       
                                                 new_node.next = head_ref;                       
                                                 head_ref = new_node;                       
                                                 head = head_ref;                       
                         }                       
           
                         // Driver Code                       
                         head =                                     null                                     ;                       
                         var                                     str =                                     "skeegforskeeg"                                     .split(                                     ""                                     );                       
                         for                                     (                                     var                                     i = 0; i < str.length; i++)                       
                         {                       
                                                 push(head, str[i]);                       
                         }                       
                         document.write(maxChar(head) +                                     "<br>"                                     );                       
           
                         // This code is contributed by rdtank                       
           
                         </script>                       

输出：

时间复杂性： （N）

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章