Moyen efficace de trouver la fréquence d'un caractère dans une chaîne en Java: O (n)

Dans une récente interview m'a demandé d'écrire le programme ci-dessous.
Découvrez le personnage dont la fréquence est de minimum dans la Chaîne ?
J'ai donc essayé en parcourant la chaîne à l'aide de charAt et de stocker le personnage clé dans une table de hachage et le nombre d'occurences de sa valeur.
Maintenant, Encore une fois, j'ai l'itération sur la Carte pour trouver le plus bas de l'élément.

Est-il un moyen plus efficace de le faire, car de toute évidence ci-dessus, on est trop intensif, je suppose.

Mise à jour et une Autre Solution

Après certains processus de pensée et les réponses, je pense que le meilleur moment que le présent peut être est O(n).
Dans la première itération, nous allons avoir à parcourir la Chaîne de caractère par caractère, puis stocker leur fréquence dans un Tableau à la position spécifique(le personnage est un int) et en même temps avoir deux variables temporaires qui maintiennent le moins compter et le caractère correspondant.Alors, quand je vais au caractère suivant et stocker sa fréquence dans les arr[char] = arr[char]+1;En même temps, je vais vérifier si la temp varible a une valeur supérieure à cette valeur,si oui, alors le temp varible sera cette valeur et aussi le char sera celui-ci.De cette façon, je suppose que nous n'avons pas besoin d'une deuxième itération de trouver le plus petit et aussi l'absence de tri est nécessaire, je suppose

.... Wat dire ? Ou plus des solutions

source d'informationauteur crackerplace

6

J'utilise un tableau plutôt qu'un hachage de la carte. Si nous sommes limités à l'ascii, c'est juste 256 entrées; si nous sommes à l'aide d'Unicode, 64 ko. De toute façon pas impossible de taille. En plus de cela, je ne vois pas comment vous pourriez améliorer votre approche. Je suis en train de penser à une astuce pour le rendre plus efficace, mais je ne peux pas venir avec de.

Me semble que la réponse est presque toujours va être toute une liste de caractères: tous ceux qui sont utilisés zéro fois.

Mise à jour

C'est probablement perdue à la plus efficace qu'il pourrait l'être dans Java. Pour plus de commodité, je suis en supposant que nous soyons à l'aide Ascii.
```
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;
}
```
Aucun effort pour garder la liste triée en fonction de la fréquence que vous allez va être plus inefficace, parce qu'elle aura pour re-trier à chaque fois que vous examinez un caractère.

Toute tentative de tri de la liste de fréquences à tout va être plus inefficace, comme le tri de l'ensemble de la liste est nettement plus lente que le simple fait de choisir la plus petite valeur.

Tri de la chaîne, puis le comptage est plus lente parce que le tri sera plus cher que le comte.

Techniquement, il serait plus rapide de créer un simple tableau à la fin plutôt qu'une liste de tableaux, mais la liste de tableaux rend un peu plus lisible le code.

Il y a peut être un moyen de faire plus vite, mais je crois que cela est proche de la solution optimale. Je serais certainement intéressé pour voir si quelqu'un a une meilleure idée.

Je pense que votre approche est la théorie la plus efficace (O(n)). Cependant, dans la pratique, il a besoin de beaucoup de mémoire, et est probablement très lent.

Il est probablement plus efficace (au moins, il utilise moins de mémoire) pour convertir la chaîne en un tableau de char, trier le tableau, puis de calculer les fréquences à l'aide d'une simple boucle. Cependant, en théorie, il est moins efficace (O(n log n)) en raison de tri (sauf si vous utilisez un plus efficace algorithme de tri).

Cas de Test:

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;
}
}

Le processus de recherche de la fréquence des caractères dans une Chaîne de caractères est très facile.

Pour toute réponse, voir mon code.

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");
}
}
}

0

Je le ferais de la manière suivante, car il implique le moins de lignes de code:

caractère que vous voulez voulez savoir la fréquence de l': "_"

Chaîne "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;
```
Vous pouvez trouver des choses bizarres qui se passerait si la chaîne commence ou se termine avec le personnage en question, mais je vais le laisser à vous de tester.
0

Avoir à parcourir la table de hachage n'est pas nécessairement mauvais. Qui ne sera O(h) où h est la table de hachage de la longueur d'--le nombre de personnages uniques-qui dans ce cas sera toujours inférieure ou égale à n. Pour l'exemple "aaabbc"h = 3 pour les trois personnages uniques. Mais, depuis h est strictement inférieur au nombre de caractères possibles: 255, elle est constante. Donc, votre grand-oh sera O(n+h) qui est en fait O(n) depuis h est constante. Je ne sais pas du tout algorithme qui pourrait obtenir un meilleur grand-oh, vous pourriez essayer d'avoir un tas de java optimisations spécifiques, mais qui dit ici est un simple algorithme que j'ai écrit qui constate le char avec la fréquence la plus basse. Il retourne "c" à partir de l'entrée "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;
}
}
```

Vous devez vous connecter pour publier un commentaire.