Encuentra el primer carácter no repetido en una cadena

¿Cuál es la forma más rápida de encontrar el primer personaje que solo aparece una vez en una cadena?

No puede saber que el personaje no se repite hasta que haya procesado toda la cadena, por lo que mi sugerencia sería esta:

def first_non_repeated_character(string): chars = [] repeated = [] for character in string: if character in chars: chars.remove(character) repeated.append(character) else: if not character in repeated: chars.append(character) if len(chars): return chars[0] else: return False 

Editar: el código publicado originalmente fue incorrecto, pero este último fragmento está Certificado para funcionar en Ryan’s Computer ™.

Tiene que ser al menos O (n) porque no sabes si un personaje se repetirá hasta que hayas leído todos los caracteres.

Para que pueda iterar sobre los caracteres y anexar cada carácter a una lista la primera vez que lo vea, y sepa por separado cuántas veces lo ha visto (de hecho, los únicos valores que importan para el recuento son “0”). , “1” o “más de 1”).

Cuando llegas al final de la cadena, solo tienes que encontrar el primer personaje de la lista que cuente exactamente uno.


Código de ejemplo en Python:

 def first_non_repeated_character(s): counts = defaultdict(int) l = [] for c in s: counts[c] += 1 if counts[c] == 1: l.append(c) for c in l: if counts[c] == 1: return c return None 

Esto se ejecuta en O (n).

¿Por qué no utilizar una estructura de datos basada en el montón como una cola de prioridad mínima? A medida que lee cada carácter de la cadena, agréguelo a la cola con una prioridad basada en la ubicación de la cadena y el número de ocurrencias hasta el momento. Puede modificar la cola para agregar prioridades en la colisión para que la prioridad de un personaje sea la sum de las apariencias numéricas de ese carácter. Al final del ciclo, el primer elemento de la cola será el carácter menos frecuente en la cadena y si hay varios caracteres con un recuento == 1, el primer elemento fue el primer carácter único agregado a la cola.

Aquí hay otra forma divertida de hacerlo. El contador requiere Python2.7 o Python3.1

 >>> from collections import Counter >>> def first_non_repeated_character(s): ... return min((k for k,v in Counter(s).items() if v<2), key=s.index) ... >>> first_non_repeated_character("aaabbbcddd") 'c' >>> first_non_repeated_character("aaaebbbcddd") 'e' 

Muchas respuestas intentan O (n) pero se olvidan de los costos reales de insertar y eliminar de las listas / conjuntos / conjuntos asociativos que están usando para rastrear.

Si puede suponer que un char es un byte único, entonces usa una matriz simple indexada por el char y mantiene un conteo en ella. Esto es realmente O (n) porque los accesos a la matriz están garantizados O (1), y el pase final sobre la matriz para encontrar el primer elemento con 1 es tiempo constante (porque la matriz tiene un tamaño pequeño y fijo).

Si no puede suponer que una char es un byte único, entonces propondría ordenar la cadena y luego hacer una única pasada verificando los valores adyacentes. Esto sería O (n log n) para el género más O (n) para el pase final. Entonces, efectivamente es O (n log n), que es mejor que O (n ^ 2). Además, prácticamente no tiene espacio adicional, lo cual es otro problema con muchas de las respuestas que intentan O (n).

El contador requiere Python2.7 o Python3.1

 >>> from collections import Counter >>> def first_non_repeated_character(s): ... counts = Counter(s) ... for c in s: ... if counts[c]==1: ... return c ... return None ... >>> first_non_repeated_character("aaabbbcddd") 'c' >>> first_non_repeated_character("aaaebbbcddd") 'e' 

Refactorizando una solución propuesta anteriormente (sin tener que usar una lista / memoria adicional). Esto pasa la cadena dos veces. Entonces esto toma O (n) también como la solución original.

 def first_non_repeated_character(s): counts = defaultdict(int) for c in s: counts[c] += 1 for c in s: if counts[c] == 1: return c return None 

La siguiente es una implementación de Ruby para encontrar el primer carácter no repetido de una cadena:

 def first_non_repeated_character(string) string1 = string.split('') string2 = string.split('') string1.each do |let1| counter = 0 string2.each do |let2| if let1 == let2 counter+=1 end end if counter == 1 return let1 break end end end p first_non_repeated_character('dont doddle in the forest') 

Y aquí hay una implementación de JavaScript de la misma función de estilo:

 var first_non_repeated_character = function (string) { var string1 = string.split(''); var string2 = string.split(''); var single_letters = []; for (var i = 0; i < string1.length; i++) { var count = 0; for (var x = 0; x < string2.length; x++) { if (string1[i] == string2[x]) { count++ } } if (count == 1) { return string1[i]; } } } console.log(first_non_repeated_character('dont doddle in the forest')); console.log(first_non_repeated_character('how are you today really?')); 

En ambos casos utilicé un contador sabiendo que si la letra no coincide en ninguna parte de la cadena, solo ocurrirá en la cadena una vez, así que solo cuento su ocurrencia.

Creo que esto debería hacerlo en C. Esto opera en el tiempo O (n) sin ambigüedad sobre el orden de los operadores de inserción y eliminación. Este es un tipo de conteo (la forma más simple de ordenación de un cubo, que en sí es la forma simple de un tipo de radix).

 unsigned char find_first_unique(unsigned char *string) { int chars[256]; int i=0; memset(chars, 0, sizeof(chars)); while (string[i++]) { chars[string[i]]++; } i = 0; while (string[i++]) { if (chars[string[i]] == 1) return string[i]; } return 0; } 

En Ruby:

(Crédito original: Andrew A. Smith)

 x = "a huge string in which some characters repeat" def first_unique_character(s) s.each_char.detect { |c| s.count(c) == 1 } end first_unique_character(x) => "u" 
 def first_non_repeated_character(string): chars = [] repeated = [] for character in string: if character in repeated: ... discard it. else if character in chars: chars.remove(character) repeated.append(character) else: if not character in repeated: chars.append(character) if len(chars): return chars[0] else: return False 

Otras soluciones de JavaScript son soluciones bastante c-style aquí es una solución más estilo de JavaScript.

 var arr = string.split(""); var occurences = {}; var tmp; var lowestindex = string.length+1; arr.forEach( function(c){ tmp = c; if( typeof occurences[tmp] == "undefined") occurences[tmp] = tmp; else occurences[tmp] += tmp; }); for(var p in occurences) { if(occurences[p].length == 1) lowestindex = Math.min(lowestindex, string.indexOf(p)); } if(lowestindex > string.length) return null; return string[lowestindex]; } 

en C, esto es casi Algoritmo de Shlemiel el Pintor (no del todo O (n!) pero más que 0 (n2)).

Pero superará a los algoritmos “mejores” para cadenas de tamaño razonable porque O es muy pequeño. Esto también puede indicarle fácilmente la ubicación de la primera cadena que no se repite.

 char FirstNonRepeatedChar(char * psz) { for (int ii = 0; psz[ii] != 0; ++ii) { for (int jj = ii+1; ; ++jj) { // if we hit the end of string, then we found a non-repeat character. // if (psz[jj] == 0) return psz[ii]; // this character doesn't repeat // if we found a repeat character, we can stop looking. // if (psz[ii] == psz[jj]) break; } } return 0; // there were no non-repeating characters. } 

editar: este código asume que no significa caracteres repetitivos consecutivos .

Aquí hay una implementación en Perl (versión> = 5.10) a la que no le importa si los caracteres repetidos son consecutivos o no:

 use strict; use warnings; foreach my $word(@ARGV) { my @distinct_chars; my %char_counts; my @chars=split(//,$word); foreach (@chars) { push @distinct_chars,$_ unless $_~~@distinct_chars; $char_counts{$_}++; } my $first_non_repeated=""; foreach(@distinct_chars) { if($char_counts{$_}==1) { $first_non_repeated=$_; last; } } if(length($first_non_repeated)) { print "For \"$word\", the first non-repeated character is '$first_non_repeated'.\n"; } else { print "All characters in \"$word\" are repeated.\n"; } } 

Almacenar este código en una secuencia de comandos (que non_repeated.pl ) y ejecutarlo en algunas entradas produce:

 jmaney> perl non_repeated.pl aabccd "a huge string in which some characters repeat" abcabc For "aabccd", the first non-repeated character is 'b'. For "a huge string in which some characters repeat", the first non-repeated character is 'u'. All characters in "abcabc" are repeated. 

Aquí hay una posible solución en ruby ​​sin usar Array#detect (como en esta respuesta ). Usar Array#detect hace demasiado fácil, creo.

 ALPHABET = %w(abcdefghijklmnopqrstu vwxyz) def fnr(s) unseen_chars = ALPHABET.dup seen_once_chars = [] s.each_char do |c| if unseen_chars.include?(c) unseen_chars.delete(c) seen_once_chars << c elsif seen_once_chars.include?(c) seen_once_chars.delete(c) end end seen_once_chars.first end 

Parece que funciona para algunos ejemplos simples:

 fnr "abcdabcegghh" # => "d" fnr "abababababababaqababa" => "q" 

Sugerencias y correcciones son muy apreciadas!

Prueba este código:

  public static String findFirstUnique(String str) { String unique = ""; foreach (char ch in str) { if (unique.Contains(ch)) unique=unique.Replace(ch.ToString(), ""); else unique += ch.ToString(); } return unique[0].ToString(); } 

En Mathematica uno podría escribir esto:

 string = "conservationist deliberately treasures analytical"; Cases[Gather @ Characters @ string, {_}, 1, 1][[1]] 
 {"v"} 

Este código de fragmento en JavaScript

 var string = "tooth"; var hash = []; for(var i=0; j=string.length, i 

Enfoque diferente aquí. Escanee cada elemento de la cadena y cree una matriz de conteo que almacene el recuento de repeticiones de cada elemento. La próxima vez, vuelva a comenzar desde el primer elemento de la matriz e imprima la primera aparición de elemento con recuento = 1

 C code ----- #include  #include  int main(int argc, char *argv[]) { char t_c; char *t_p = argv[1] ; char count[128]={'\0'}; char ch; for(t_c = *(argv[1]); t_c != '\0'; t_c = *(++t_p)) count[t_c]++; t_p = argv[1]; for(t_c = *t_p; t_c != '\0'; t_c = *(++t_p)) { if(count[t_c] == 1) { printf("Element is %c\n",t_c); break; } } return 0; } 

la entrada es = salida aabbcddeef es = c

 char FindUniqueChar(char *a) { int i=0; bool repeat=false; while(a[i] != '\0') { if (a[i] == a[i+1]) { repeat = true; } else { if(!repeat) { cout< 

Aquí hay otro enfoque … podríamos tener una matriz que almacenará el recuento y el índice de la primera aparición del personaje. Después de completar el conjunto, podríamos atravesar el conjunto y encontrar el índice MÍNIMO cuyo recuento es 1 y luego regresar a str [índice]

 #include  #include  #include  #include  using namespace std; #define No_of_chars 256 //store the count and the index where the char first appear typedef struct countarray { int count; int index; }countarray; //returns the count array countarray *getcountarray(char *str) { countarray *count; count=new countarray[No_of_chars]; for(int i=0;i array[i].index) result = array[i].index; } delete[] (array); return (str[result]); } int main() { char str[] = "geeksforgeeks"; cout<<"First non repeating character is "< 

Función:

Esta función c # usa una HashTable (Diccionario) y tiene un peor comportamiento O (2n).

 private static string FirstNoRepeatingCharacter(string aword) { Dictionary dic = new Dictionary(); for (int i = 0; i < aword.Length; i++) { if (!dic.ContainsKey(aword.Substring(i, 1))) dic.Add(aword.Substring(i, 1), 1); else dic[aword.Substring(i, 1)]++; } foreach (var item in dic) { if (item.Value == 1) return item.Key; } return string.Empty; } 

Ejemplo:

string aword = "TEETER";

Console.WriteLine (FirstNoRepeatingCharacter (aword)); // imprimir: R

Tengo dos cadenas, es decir, ‘único’ y ‘repetido’. Cada personaje que aparece por primera vez, se agrega a ‘único’. Si se repite por segunda vez, se elimina de ‘único’ y se agrega a ‘repetido’. De esta manera, siempre tendremos una cadena de caracteres únicos en ‘único’. Complejidad grande O (n)

 public void firstUniqueChar(String str){ String unique= ""; String repeated = ""; str = str.toLowerCase(); for(int i=0; i 

El siguiente código está en C # con la complejidad de n.

 using System; using System.Linq; using System.Text; namespace SomethingDigital { class FirstNonRepeatingChar { public static void Main() { String input = "geeksforgeeksandgeeksquizfor"; char[] str = input.ToCharArray(); bool[] b = new bool[256]; String unique1 = ""; String unique2 = ""; foreach (char ch in str) { if (!unique1.Contains(ch)) { unique1 = unique1 + ch; unique2 = unique2 + ch; } else { unique2 = unique2.Replace(ch.ToString(), ""); } } if (unique2 != "") { Console.WriteLine(unique2[0].ToString()); Console.ReadLine(); } else { Console.WriteLine("No non repeated string"); Console.ReadLine(); } } } } 

La siguiente solución es una manera elegante de encontrar el primer carácter único dentro de una cadena usando las nuevas características que se han introducido como parte de Java 8. Esta solución usa el enfoque de crear primero un mapa para contar el número de ocurrencias de cada personaje. Luego usa este mapa para encontrar el primer personaje que aparece solo una vez. Esto se ejecuta en O (N) tiempo.

 import static java.util.stream.Collectors.counting; import static java.util.stream.Collectors.groupingBy; import java.util.Arrays; import java.util.List; import java.util.Map; // Runs in O(N) time and uses lambdas and the stream API from Java 8 // Also, it is only three lines of code! private static String findFirstUniqueCharacterPerformantWithLambda(String inputString) { // convert the input string into a list of characters final List inputCharacters = Arrays.asList(inputString.split("")); // first, construct a map to count the number of occurrences of each character final Map characterCounts = inputCharacters .stream() .collect(groupingBy(s -> s, counting())); // then, find the first unique character by consulting the count map return inputCharacters .stream() .filter(s -> characterCounts.get(s) == 1) .findFirst() .orElse(null); } 

Aquí hay una solución más con o (n) complejidad de tiempo.

 public void findUnique(String string) { ArrayList uniqueList = new ArrayList<>(); int[] chatArr = new int[128]; for (int i = 0; i < string.length(); i++) { Character ch = string.charAt(i); if (chatArr[ch] != -1) { chatArr[ch] = -1; uniqueList.add(ch); } else { uniqueList.remove(ch); } } if (uniqueList.size() == 0) { System.out.println("No unique character found!"); } else { System.out.println("First unique character is :" + uniqueList.get(0)); } } 

Leí las respuestas, pero no vi ninguna como la mía, creo que esta es muy simple y rápida, ¿me equivoco?

 def first_unique(s): repeated = [] while s: if s[0] not in s[1:] and s[0] not in repeated: return s[0] else: repeated.append(s[0]) s = s[1:] return None 

prueba

 (first_unique('abdcab') == 'd', first_unique('aabbccdad') == None, first_unique('') == None, first_unique('a') == 'a') 

Pregunta: Primer carácter único de una cadena Esta es la solución más simple.

 public class Test4 { public static void main(String[] args) { String a = "GiniGinaProtijayi"; firstUniqCharindex(a); } public static void firstUniqCharindex(String a) { int[] count = new int[256]; for (int i = 0; i < a.length(); i++) { count[a.charAt(i)]++; } int index = -1; for (int i = 0; i < a.length(); i++) { if (count[a.charAt(i)] == 1) { index = i; break; } // if } System.out.println(index);// output => 8 System.out.println(a.charAt(index)); //output => P }// end1 } 

EN Python:

 def firstUniqChar(a): count = [0] * 256 for i in a: count[ord(i)] += 1 element = "" for items in a: if(count[ord(items) ] == 1): element = items ; break return element a = "GiniGinaProtijayi"; print(firstUniqChar(a)) # output is P 

¿Qué hay de usar un árbol de sufijo para este caso … el primer carácter sin repetición será el primer personaje de la cadena de sufijo más larga con la menor profundidad en el árbol …

Crear dos listas –

  1. lista única, que tiene un carácter único … UL
  2. lista no única: tener solo caracteres repetidos -NUL
   para (char c en str) {
     if (nul.contains (c)) {
      //hacer nada
     } else if (ul.contains (c)) {
       ul.remove (c);
       nul.add (c);
     }más{
        nul.add (c);
     }