从字符流中查找第一个非重复字符-yiteyi-C++库

给定一个字符流，从该流中找到第一个非重复字符。你需要随时说出O（1）时间内的第一个非重复字符。

null

如果我们遵循讨论的第一种方法在这里，然后我们需要存储流，以便我们可以再次遍历它，以便随时找到第一个非重复字符。如果我们使用同一职位，每次查询第一个非重复元素时，我们都需要遍历count数组。我们可以随时从流中找到第一个非重复字符，而无需遍历任何数组。

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

我们的想法是使用动态链接库 ( D 双倍 L 墨水 L ist）以有效地从流中获取第一个非重复字符。DLL按顺序包含所有非重复字符，即DLL头包含第一个非重复字符，第二个节点包含第二个非重复字符，依此类推。

我们还维护两个数组：一个数组是维护已经访问了两次或更多次的字符，我们称之为repeated[]，另一个数组是指向链表节点的指针数组，我们称之为inDLL[]。两个数组的大小都等于字母表大小，通常为256。

创建一个空DLL。另外，创建两个大小为256的数组inDLL[]和repeated[]。In DLL是指向DLL节点的指针数组。repeated[]是一个布尔数组，如果x重复两次或多次，repeated[x]为真，否则为假。如果DLL中存在字符x，则inDLL[x]包含指向DLL节点的指针，否则为NULL。
将inDLL[]的所有条目初始化为NULL，并将重复的[]初始化为false。
要获取第一个非重复字符，请返回DLL开头的字符。
以下是处理流中新字符“x”的步骤。
- 如果repeated[x]为真，则忽略此字符（x已在流中重复两次或更多次）
- 如果repeated[x]为false，inDLL[x]为NULL（x第一次出现）。将x附加到DLL，并将新DLL节点的地址存储在inDLL[x]中。
- 如果repeated[x]为false，且inDLL[x]不为NULL（第二次看到x）。使用inDLL[x]获取x的DLL节点并删除该节点。此外，将inDLL[x]标记为NULL，并将[x]重复标记为true。

请注意，将新节点附加到DLL O（1） 如果我们保持一个尾部指针。从DLL中删除一个节点也很重要 O（1） .因此，添加新字符和查找第一个非重复字符这两个操作都需要 O（1） 时间

下图是上述方法的试运行：

图片[1]-从字符流中查找第一个非重复字符-yiteyi-C++库图片[2]-从字符流中查找第一个非重复字符-yiteyi-C++库图片[3]-从字符流中查找第一个非重复字符-yiteyi-C++库图片[4]-从字符流中查找第一个非重复字符-yiteyi-C++库图片[5]-从字符流中查找第一个非重复字符-yiteyi-C++库图片[6]-从字符流中查找第一个非重复字符-yiteyi-C++库

以下是上述方法的实施情况：

C++

                         // A C++ program to find first                       
                         // non-repeating character                       
                         // from a stream of characters                       
                         #include <iostream>                       
                         #define MAX_CHAR 256                       
                         using                                     namespace                                     std;                       
           
                         // A linked list node                       
                         struct                                     node {                       
                                                 char                                     a;                       
                                                 struct                                     node *next, *prev;                       
                         };                       
           
                         // A utility function to append a character x at the end                       
                         // of DLL. Note that the function may change head and tail                       
                         // pointers, that is why pointers to these pointers are                       
                         // passed.                       
                         void                                     appendNode(                                     struct                                     node** head_ref,                       
                                                 struct                                     node** tail_ref,                                     char                                     x)                       
                         {                       
                                                 struct                                     node* temp =                                     new                                     node;                       
                                                 temp->a = x;                       
                                                 temp->prev = temp->next = NULL;                       
           
                                                 if                                     (*head_ref == NULL) {                       
                                                 *head_ref = *tail_ref = temp;                       
                                                 return                                     ;                       
                                                 }                       
                                                 (*tail_ref)->next = temp;                       
                                                 temp->prev = *tail_ref;                       
                                                 *tail_ref = temp;                       
                         }                       
           
                         // A utility function to remove a node 'temp' from DLL.                       
                         // Note that the function may change the head and tail pointers,                       
                         // that is why pointers to these pointers are passed.                       
                         void                                     removeNode(                                     struct                                     node** head_ref,                       
                                                 struct                                     node** tail_ref,                                     struct                                     node* temp)                       
                         {                       
                                                 if                                     (*head_ref == NULL)                       
                                                 return                                     ;                       
           
                                                 if                                     (*head_ref == temp)                       
                                                 *head_ref = (*head_ref)->next;                       
                                                 if                                     (*tail_ref == temp)                       
                                                 *tail_ref = (*tail_ref)->prev;                       
                                                 if                                     (temp->next != NULL)                       
                                                 temp->next->prev = temp->prev;                       
                                                 if                                     (temp->prev != NULL)                       
                                                 temp->prev->next = temp->next;                       
           
                                                 delete                                     (temp);                       
                         }                       
           
                         void                                     findFirstNonRepeating()                       
                         {                       
                                                 // inDLL[x] contains pointer to                       
                                                 // a DLL node if x is present                       
                                                 // in DLL. If x is not present, then inDLL[x] is NULL                       
                                                 struct                                     node* inDLL[MAX_CHAR];                       
           
                                                 // repeated[x] is true if x is repeated two or more                       
                                                 // times. If x is not seen so far or x is seen only                       
                                                 // once. then repeated[x] is false                       
                                                 bool                                     repeated[MAX_CHAR];                       
           
                                                 // Initialize the above two arrays                       
                                                 struct                                     node *head = NULL, *tail = NULL;                       
                                                 for                                     (                                     int                                     i = 0; i < MAX_CHAR; i++) {                       
                                                 inDLL[i] = NULL;                       
                                                 repeated[i] =                                     false                                     ;                       
                                                 }                       
           
                                                 // Let us consider following stream and see the process                       
                                                 char                                     stream[] =                                     "geeksforgeeksandgeeksquizfor"                                     ;                       
                                                 for                                     (                                     int                                     i = 0; stream[i]; i++) {                       
                                                 char                                     x = stream[i];                       
                                                 cout <<                                     "Reading "                                     << x <<                                     " from stream "                                     ;                       
           
                                                 // We process this character only if it has not                       
                                                 // occurred or occurred only once. repeated[x] is                       
                                                 // true if x is repeated twice or more.s                       
                                                 if                                     (!repeated[x]) {                       
                                                 // If the character is not in DLL, then add this                       
                                                 // at the end of DLL.                       
                                                 if                                     (inDLL[x] == NULL) {                       
                                                 appendNode(&head, &tail, stream[i]);                       
                                                 inDLL[x] = tail;                       
                                                 }                       
                                                 else                                     // Otherwise remove this character from DLL                       
                                                 {                       
                                                 removeNode(&head, &tail, inDLL[x]);                       
                                                 inDLL[x] = NULL;                       
                                                 repeated[x]                       
                                                 =                                     true                                     ;                                     // Also mark it as repeated                       
                                                 }                       
                                                 }                       
           
                                                 // Print the current first non-repeating character                       
                                                 // from stream                       
                                                 if                                     (head != NULL)                       
                                                 cout <<                                     "First non-repeating character so far "                       
                                                 "is "                       
                                                 << head->a << endl;                       
                                                 }                       
                         }                       
           
                         /* Driver code */                       
                         int                                     main()                       
                         {                       
                                                 findFirstNonRepeating();                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // A Java program to find first non-repeating character                       
                         // from a stream of characters                       
           
                         import                                     java.util.ArrayList;                       
                         import                                     java.util.List;                       
           
                         public                                     class                                     NonReapeatingC {                       
                                                 final                                     static                                     int                                     MAX_CHAR =                                     256                                     ;                       
           
                                                 static                                     void                                     findFirstNonRepeating()                       
                                                 {                       
                                                 // inDLL[x] contains pointer to a DLL node if x is                       
                                                 // present in DLL. If x is not present, then                       
                                                 // inDLL[x] is NULL                       
                                                 List<Character> inDLL =                                     new                                     ArrayList<Character>();                       
           
                                                 // repeated[x] is true if x is repeated two or more                       
                                                 // times. If x is not seen so far or x is seen only                       
                                                 // once. then repeated[x] is false                       
                                                 boolean                                     [] repeated =                                     new                                     boolean                                     [MAX_CHAR];                       
           
                                                 // Let us consider following stream and see the                       
                                                 // process                       
                                                 String stream =                                     "geeksforgeeksandgeeksquizfor"                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < stream.length(); i++) {                       
                                                 char                                     x = stream.charAt(i);                       
                                                 System.out.println(                                     "Reading "                                     + x                       
                                                 +                                     " from stream "                                     );                       
           
                                                 // We process this character only if it has not                       
                                                 // occurred or occurred only once. repeated[x]                       
                                                 // is true if x is repeated twice or more.s                       
                                                 if                                     (!repeated[x]) {                       
                                                 // If the character is not in DLL, then add                       
                                                 // this at the end of DLL.                       
                                                 if                                     (!(inDLL.contains(x))) {                       
                                                 inDLL.add(x);                       
                                                 }                       
                                                 else                                     // Otherwise remove this character from                       
                                                 // DLL                       
                                                 {                       
                                                 inDLL.remove((Character)x);                       
                                                 repeated[x]                       
                                                 =                                     true                                     ;                                     // Also mark it as repeated                       
                                                 }                       
                                                 }                       
           
                                                 // Print the current first non-repeating                       
                                                 // character from stream                       
                                                 if                                     (inDLL.size() !=                                     0                                     ) {                       
                                                 System.out.print(                       
                                                 "First non-repeating character so far is "                                     );                       
                                                 System.out.println(inDLL.get(                                     0                                     ));                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 /* Driver code */                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 findFirstNonRepeating();                       
                                                 }                       
                         }                       
                         // This code is contributed by Sumit Ghosh                       

Python3

                         # A Python program to find first non-repeating character from                       
                         # a stream of characters                       
                         MAX_CHAR                                     =                                     256                       
           
                         def                                     findFirstNonRepeating():                       
           
                                                 # inDLL[x] contains pointer to a DLL node if x is present                       
                                                 # in DLL. If x is not present, then inDLL[x] is NULL                       
                                                 inDLL                                     =                                     []                                     *                                     MAX_CHAR                       
           
                                                 # repeated[x] is true if x is repeated two or more times.                       
                                                 # If x is not seen so far or x is seen only once. then                       
                                                 # repeated[x] is false                       
                                                 repeated                                     =                                     [                                     False                                     ]                                     *                                     MAX_CHAR                       
           
                                                 # Let us consider following stream and see the process                       
                                                 stream                                     =                                     "geekforgeekandgeeksandquizfor"                       
                                                 for                                     i                                     in                                     range                                     (                                     len                                     (stream)):                       
                                                 x                                     =                                     stream[i]                       
                                                 print                                     (                                     "Reading "                                     +                                     x                                     +                                     " from stream"                                     )                       
           
                                                 # We process this character only if it has not occurred                       
                                                 # or occurred only once. repeated[x] is true if x is                       
                                                 # repeated twice or more.s                       
                                                 if                                     not                                     repeated[                                     ord                                     (x)]:                       
           
                                                 # If the character is not in DLL, then add this                       
                                                 # at the end of DLL                       
                                                 if                                     not                                     x                                     in                                     inDLL:                       
                                                 inDLL.append(x)                       
                                                 else                                     :                       
                                                 inDLL.remove(x)                       
                                                 repeated[                                     ord                                     (x)]                                     =                                     True                       
           
                                                 if                                     len                                     (inDLL) !                                     =                                     0                                     :                       
                                                 print                                     (                                     "First non-repeating character so far is "                                     )                       
                                                 print                                     (                                     str                                     (inDLL[                                     0                                     ]))                       
           
                         # Driver program                       
                         findFirstNonRepeating()                       
           
                         # This code is contributed by BHAVYA JAIN                       

C#

                         // A C# program to find first non-repeating character                       
                         // from a stream of characters                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         public                                     class                                     NonReapeatingC {                       
                                                 readonly                                     static                                     int                                     MAX_CHAR = 256;                       
           
                                                 static                                     void                                     findFirstNonRepeating()                       
                                                 {                       
                                                 // inDLL[x] contains pointer to a DLL node if x is present                       
                                                 // in DLL. If x is not present, then inDLL[x] is NULL                       
                                                 List<                                     char                                     > inDLL =                                     new                                     List<                                     char                                     >();                       
           
                                                 // repeated[x] is true if x is repeated two or more times.                       
                                                 // If x is not seen so far or x is seen only once. then                       
                                                 // repeated[x] is false                       
                                                 bool                                     [] repeated =                                     new                                     bool                                     [MAX_CHAR];                       
           
                                                 // Let us consider following stream and see the process                       
                                                 String stream =                                     "geeksforgeeksandgeeksquizfor"                                     ;                       
                                                 for                                     (                                     int                                     i = 0; i < stream.Length; i++) {                       
                                                 char                                     x = stream[i];                       
                                                 Console.WriteLine(                                     "Reading "                                     + x +                                     " from stream "                                     );                       
           
                                                 // We process this character only if it has not occurred                       
                                                 // or occurred only once. repeated[x] is true if x is                       
                                                 // repeated twice or more.s                       
                                                 if                                     (!repeated[x]) {                       
                                                 // If the character is not in DLL, then add this at                       
                                                 // the end of DLL.                       
                                                 if                                     (!(inDLL.Contains(x))) {                       
                                                 inDLL.Add(x);                       
                                                 }                       
                                                 else                                     // Otherwise remove this character from DLL                       
                                                 {                       
                                                 inDLL.Remove((                                     char                                     )x);                       
                                                 repeated[x] =                                     true                                     ;                                     // Also mark it as repeated                       
                                                 }                       
                                                 }                       
           
                                                 // Print the current first non-repeating character from                       
                                                 // stream                       
                                                 if                                     (inDLL.Count != 0) {                       
                                                 Console.Write(                                     "First non-repeating character so far is "                                     );                       
                                                 Console.WriteLine(inDLL[0]);                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 /* Driver code*/                       
                                                 public                                     static                                     void                                     Main(String[] args)                       
                                                 {                       
                                                 findFirstNonRepeating();                       
                                                 }                       
                         }                       
           
                         // This code has been contributed by 29AjayKumar                       

Javascript

                         <script>                       
           
                         // A Javascript program to find first                       
                         // non-repeating character from a                       
                         // stream of characters                       
                         let MAX_CHAR = 256;                       
           
                         function                                     findFirstNonRepeating()                       
                         {                       
                                   
                                                 // inDLL[x] contains pointer to a DLL                       
                                                 // node if x is present in DLL. If x                       
                                                 // is not present, then inDLL[x] is NULL                       
                                                 let inDLL = [];                       
           
                                                 // repeated[x] is true if x is repeated                       
                                                 // two or more times. If x is not seen                       
                                                 // so far or x is seen only once.                       
                                                 // then repeated[x] is false                       
                                                 let repeated =                                     new                                     Array(MAX_CHAR);                       
                                                 for                                     (let i = 0; i < MAX_CHAR; i++)                       
                                                 {                       
                                                 repeated[i] =                                     false                                     ;                       
                                                 }                       
                                   
                                                 // Let us consider following stream and see the                       
                                                 // process                       
                                                 let stream =                                     "geeksforgeeksandgeeksquizfor"                                     ;                       
                                                 for                                     (let i = 0; i < stream.length; i++)                       
                                                 {                       
                                                 let x = stream[i];                       
                                                 document.write(                                     "Reading "                                     + x +                       
                                                 " from stream <br>"                                     );                       
           
                                                 // We process this character only if it has not                       
                                                 // occurred or occurred only once. repeated[x]                       
                                                 // is true if x is repeated twice or more.s                       
                                                 if                                     (!repeated[x.charCodeAt(0)])                       
                                                 {                       
                                   
                                                 // If the character is not in DLL, then add                       
                                                 // this at the end of DLL.                       
                                                 if                                     (!(inDLL.includes(x)))                       
                                                 {                       
                                                 inDLL.push(x);                       
                                                 }                       
                                   
                                                 // Otherwise remove this character from                       
                                                 // DLL                       
                                                 else                       
                                                 {                       
                                                 inDLL.splice(inDLL.indexOf(x), 1);                       
                                   
                                                 // Also mark it as repeated                       
                                                 repeated[x.charCodeAt(0)] =                                     true                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // Print the current first non-repeating                       
                                                 // character from stream                       
                                                 if                                     (inDLL.length != 0)                       
                                                 {                       
                                                 document.write(                                     "First non-repeating "                                     +                       
                                                 "character so far is "                                     );                       
                                                 document.write(inDLL[0] +                                     "<br>"                                     );                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         findFirstNonRepeating();                       
           
                         // This code is contributed by rag2127                       
           
                         </script>                       

输出：

Reading g from streamFirst non-repeating character so far is gReading e from streamFirst non-repeating character so far is gReading e from streamFirst non-repeating character so far is gReading k from streamFirst non-repeating character so far is gReading s from streamFirst non-repeating character so far is gReading f from streamFirst non-repeating character so far is gReading o from streamFirst non-repeating character so far is gReading r from streamFirst non-repeating character so far is gReading g from streamFirst non-repeating character so far is kReading e from streamFirst non-repeating character so far is kReading e from streamFirst non-repeating character so far is kReading k from streamFirst non-repeating character so far is sReading s from streamFirst non-repeating character so far is fReading a from streamFirst non-repeating character so far is fReading n from streamFirst non-repeating character so far is fReading d from streamFirst non-repeating character so far is fReading g from streamFirst non-repeating character so far is fReading e from streamFirst non-repeating character so far is fReading e from streamFirst non-repeating character so far is fReading k from streamFirst non-repeating character so far is fReading s from streamFirst non-repeating character so far is fReading q from streamFirst non-repeating character so far is fReading u from streamFirst non-repeating character so far is fReading i from streamFirst non-repeating character so far is fReading z from streamFirst non-repeating character so far is fReading f from streamFirst non-repeating character so far is oReading o from streamFirst non-repeating character so far is rReading r from streamFirst non-repeating character so far is a

本文由 阿密特·贾恩 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。

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

THE END

Python