Dada una secuencia de caracteres, encuentre el primer carácter que no se repite de la secuencia. Debe indicar el primer carácter que no se repite en el tiempo O (1) en cualquier momento.
Si seguimos el primer enfoque discutido aquí , entonces necesitamos almacenar el flujo para que podamos atravesarlo una vez más para encontrar el primer carácter que no se repite en cualquier momento. Si usamos el enfoque extendido discutido en la misma publicación , debemos revisar la array de conteo cada vez que se consulta el primer elemento que no se repite. Podemos encontrar el primer carácter no repetido de la secuencia en cualquier momento sin atravesar ninguna array.
La idea es utilizar una DLL ( Lista de enlaces dobles ) para obtener de manera eficiente el primer carácter que no se repite de una secuencia. La DLL contiene todos los caracteres que no se repiten en orden, es decir, el encabezado de la DLL contiene el primer carácter que no se repite, el segundo Node contiene el segundo que no se repite, y así sucesivamente.
También mantenemos dos arrays: una array es para mantener los caracteres que ya han sido visitados dos o más veces, la llamamos repeat[], la otra array es una array de punteros a Nodes de listas enlazadas, la llamamos inDLL[]. El tamaño de ambas arrays es igual al tamaño del alfabeto, que normalmente es 256.
- Cree una DLL vacía. Además, cree dos arrays en DLL[] y repeat[] de tamaño 256. En DLL hay una array de punteros a Nodes DLL. repetido[] es una array booleana, repetido[x] es verdadero si x se repite dos o más veces, de lo contrario, falso. inDLL[x] contiene un puntero a un Node DLL si el carácter x está presente en DLL, de lo contrario, NULL.
- Inicializa todas las entradas de inDLL[] como NULL y repite [] como falso.
- Para obtener el primer carácter que no se repite, devuelva el carácter al principio de la DLL.
- Los siguientes son los pasos para procesar un nuevo carácter ‘x’ en una secuencia.
- Si repeat[x] es verdadero, ignore este carácter (x ya se repite dos o más veces en la secuencia)
- Si repeat[x] es falso e inDLL[x] es NULL (x se ve la primera vez). Agregue x a la DLL y almacene la dirección del nuevo Node DLL en inDLL[x].
- Si repeat[x] es falso e inDLL[x] no es NULL (x se ve por segunda vez). Obtenga el Node DLL de x usando inDLL[x] y elimine el Node. Además, marque inDLL[x] como NULL y repeat[x] como verdadero.
Tenga en cuenta que agregar un nuevo Node a DLL es una operación O (1) si mantenemos un puntero de cola. Eliminar un Node de DLL también es O(1) . Entonces, ambas operaciones, la adición de un nuevo carácter y la búsqueda del primer carácter que no se repite, toman un tiempo O (1) .
La imagen de abajo es una ejecución en seco del enfoque anterior:
A continuación se muestra la implementación del enfoque anterior:
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 \n";
// 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 \n");
// 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 \n");
// 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>
Producción:
Reading g from stream First non-repeating character so far is g Reading e from stream First non-repeating character so far is g Reading e from stream First non-repeating character so far is g Reading k from stream First non-repeating character so far is g Reading s from stream First non-repeating character so far is g Reading f from stream First non-repeating character so far is g Reading o from stream First non-repeating character so far is g Reading r from stream First non-repeating character so far is g Reading g from stream First non-repeating character so far is k Reading e from stream First non-repeating character so far is k Reading e from stream First non-repeating character so far is k Reading k from stream First non-repeating character so far is s Reading s from stream First non-repeating character so far is f Reading a from stream First non-repeating character so far is f Reading n from stream First non-repeating character so far is f Reading d from stream First non-repeating character so far is f Reading g from stream First non-repeating character so far is f Reading e from stream First non-repeating character so far is f Reading e from stream First non-repeating character so far is f Reading k from stream First non-repeating character so far is f Reading s from stream First non-repeating character so far is f Reading q from stream First non-repeating character so far is f Reading u from stream First non-repeating character so far is f Reading i from stream First non-repeating character so far is f Reading z from stream First non-repeating character so far is f Reading f from stream First non-repeating character so far is o Reading o from stream First non-repeating character so far is r Reading r from stream First non-repeating character so far is a
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Este artículo es una contribución de Amit Jain . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA