Manera eficiente de encontrar la Frecuencia de un personaje en una Cadena en java: O (n)

Question

En una entrevista reciente me pidieron que escribiera el siguiente programa. Descubre el personaje cuya frecuencia es mínima en la cadena dada? Así que intenté iterando a través de la cadena utilizando charAt y almacenando el carácter como clave en un HashMap y el número de ocurrencias como su valor. Ahora otra vez tengo que repetir en el mapa para encontrar el elemento más bajo.

Hay una manera más eficiente de hacerlo ya que, obviamente, el anterior es demasiado intensivo, supongo.

Actualización y otra solución

Después de un proceso de pensamiento y respuestas creo que el mejor momento que este puede ser es O (n). En la primera iteración tendremos que iterar a través de la Cadena carácter por carácter y luego almacenar su frecuencia en una Matriz en la posición específica (el carácter es un int) y al mismo tiempo tener dos variables temporales que mantienen el conteo menor y el carácter correspondiente Así que cuando voy al siguiente caracter y almaceno su frecuencia en arr [char] = arr [char] +1; Al mismo tiempo verificaré si la variable temporal tiene un valor mayor que este valor, si es así, entonces la temperatura varible será este valor y también el char será este. De esta manera, supongo que no necesitamos una segunda iteración para encontrar el más pequeño y tampoco se requiere ordenamiento Supongo

.... ¿Qué dice? O más soluciones

Answer 1

Utilizaría una matriz en lugar de un mapa hash. Si estamos limitados a ascii, eso es solo 256 entradas; si estamos usando Unicode, 64k. De cualquier manera, no es un tamaño imposible. Además de eso, no veo cómo podrías mejorar tu enfoque. Estoy tratando de pensar en algún truco inteligente para hacerlo más eficiente, pero no puedo pensar en ninguno.

Me parece que la respuesta casi siempre será una lista completa de caracteres: todos los que se usan cero veces.

actualización

Ésta es probablemente infundada pues a la más eficiente que podría ser en Java. Por conveniencia, asumo que estamos usando Ascii simple.

public List<Character> rarest(String s) 
{ 
    int[] freq=new int[256]; 

    for (int p=s.length()-1;p>=0;--p) 
    { 
    char c=s.charAt(p); 
    if (c>255) 
     throw new UnexpectedDataException("Wasn't expecting that"); 
    ++freq[c]; 
    } 
    int min=Integer.MAX_VALUE; 
    for (int x=freq.length-1;x>=0;--x) 
    { 
    // I'm assuming we don't want chars with frequency of zero 
    if (freq[x]>0 && min>freq[x]) 
     min=freq[x]; 
    } 
    List<Character> rares=new ArrayList<Character>(); 
    for (int x=freq.length-1;x>=0;--x) 
    { 
    if (freq[x]==min) 
     rares.add((char)x); 
    } 
    return rares; 
} 

Cualquier esfuerzo por mantener la lista ordenada por frecuencia a medida que avanza va a ser la forma más ineficiente, ya que tendrá que volver a ordenar cada vez que se examina un carácter.

Cualquier intento de ordenar la lista de frecuencias va a ser más ineficiente, ya que la ordenación de toda la lista va a ser más lenta que simplemente elegir el valor más pequeño.

La clasificación de la cuerda y el recuento van a ser más lentos porque la clasificación será más costosa que la cuenta.

Técnicamente, sería más rápido crear una matriz simple al final en lugar de una ArrayList, pero ArrayList hace un código ligeramente más legible.

Puede haber una manera de hacerlo más rápido, pero sospecho que está cerca de la solución óptima. Ciertamente me interesaría ver si alguien tiene una mejor idea.

Answer 2

Creo que su enfoque es en teoría el más eficiente (O (n)). Sin embargo, en la práctica, necesita mucha memoria y probablemente sea muy lenta.

Posiblemente sea más eficiente (al menos use menos memoria) para convertir la cadena en una matriz de caracteres, ordenar la matriz y luego calcular las frecuencias usando un bucle simple. Sin embargo, en teoría es menos eficiente (O (n log n)) debido a la clasificación (a menos que use un algoritmo de clasificación más eficiente).

caso de prueba:

import java.util.Arrays; 

public class Test { 

    public static void main(String... args) throws Exception { 
     //  System.out.println(getLowFrequencyChar("x")); 
     //  System.out.println(getLowFrequencyChar("bab")); 
     //  System.out.println(getLowFrequencyChar("babaa")); 
     for (int i = 0; i < 5; i++) { 
      long start = System.currentTimeMillis(); 
      for (int j = 0; j < 1000000; j++) { 
       getLowFrequencyChar("long start = System.currentTimeMillis();"); 
      } 
      System.out.println(System.currentTimeMillis() - start); 
     } 

    } 

    private static char getLowFrequencyChar(String string) { 
     int len = string.length(); 
     if (len == 0) { 
      return 0; 
     } else if (len == 1) { 
      return string.charAt(0); 
     } 
     char[] chars = string.toCharArray(); 
     Arrays.sort(chars); 
     int low = Integer.MAX_VALUE, f = 1; 
     char last = chars[0], x = 0; 
     for (int i = 1; i < len; i++) { 
      char c = chars[i]; 
      if (c != last) { 
       if (f < low) { 
        if (f == 1) { 
         return last; 
        } 
        low = f; 
        x = last; 
       } 
       last = c; 
       f = 1; 
      } else { 
       f++; 
      } 
     } 
     if (f < low) { 
      x = last; 
     } 
     return (char) x; 
    } 

} 

Answer 3

me gustaría hacerlo de la siguiente manera, ya que implica menor número de las líneas de código:

carácter que tiene que quieran conocer la frecuencia de: "_"
cadena "this_is_a_test"

String testStr = "this_is_a_test"; 
String[] parts = testStr.split("_"); //note you need to use regular expressions here 
int freq = parts.length -1; 

Usted puede encontrar cosas extrañas suceden si la cadena se inicia o termina con el personaje en cuestión, pero voy a dejar que se a probar para eso.

Answer 4

El proceso de búsqueda de la frecuencia de caracteres en una cadena es muy fácil.
Para la respuesta vea mi código.

import java.io.*; 
public class frequency_of_char 
{ 
    public static void main(String args[])throws IOException 
    { 
     BufferedReader in=new BufferedReader(new InputStreamReader(System.in)); 
     int ci,i,j,k,l;l=0; 
     String str,str1; 
     char c,ch; 
     System.out.println("Enter your String"); 
     str=in.readLine(); 
     i=str.length(); 
     for(c='A';c<='z';c++) 
     { 
      k=0; 
      for(j=0;j<i;j++) 
      { 
       ch=str.charAt(j); 
       if(ch==c) 
        k++; 
      } 
      if(k>0) 
      System.out.println("The character "+c+" has occured for "+k+" times"); 
     } 
    } 
} 

Answer 5

Tener que iterar a través del HashMap no es necesariamente malo. Eso solo será O(h) donde h es la longitud del HashMap, el número de caracteres únicos, que en este caso siempre será menor o igual que n. Para el ejemplo "aaabbc", h = 3 para los tres caracteres únicos. Pero, dado que h es estrictamente menor que el número de caracteres posibles: 255, es constante. Por lo tanto, su big-oh será O(n+h) que en realidad es O(n) ya que h es constante. No sé de ningún algoritmo que pueda mejorarse mucho -oh, podrías tratar de tener un montón de optimizaciones específicas de Java, pero eso dicho aquí es un algoritmo simple que escribí que encuentra el char con la frecuencia más baja. Devuelve "c" desde la entrada "aaabbc".

import java.util.HashMap; 
import java.util.Map; 

public class StackOverflowQuestion { 

public static void main(String[] args) { 
    // TODO Auto-generated method stub 

    System.out.println("" + findLowestFrequency("aaabbc")); 

} 

public static char findLowestFrequency(String input) { 

    Map<Character, Integer> map = new HashMap<Character, Integer>(); 

    for (char c : input.toCharArray()) 

     if (map.containsKey(c)) 
      map.put(c, map.get(c) + 1); 
     else 
      map.put(c, 0); 

    char rarest = map.keySet().iterator().next(); 

    for (char c : map.keySet()) 

     if (map.get(c) < map.get(rarest)) 
      rarest = c; 

    return rarest; 

} 

}