Finden Sie die Frequenz des Zeichens in ein array von Strings
Gegeben ein array von Strings, finden die Häufigkeit des Auftretens eines bestimmten Zeichens.
zB. Angesichts array {"hon","bhig","zzz","Hallo"} und-Zeichen 'h', die Ausgabe ist 3.
Hier ist, wie ich es gelöst:
Ansatz 1: Durchlaufen und jeder string in dem array, Inkrementieren eines Zählers jedes mal, dass der Charakter tritt in der aktuellen Zeichenfolge. Laufzeit ist O(n), wobei n die kumulative Länge aller strings in dem array.
Ansatz 2: Dieser kann optimiert werden indem eine HashMap; dies ist besonders hilfreich, wenn die Saiten wiederholt in das array. Hier ist, was ich Tat: nehmen Sie sich eine HashMap, wo key = string und Wert = Anzahl der Zeiten, die Zeichenfolge tritt in das array. Setzen Sie alle Zeichenfolgen, die in dem gegebenen array in die HashMap zusammen mit Ihren zählt. Dann Durchlaufen Sie jedes Schlüssel-Wert-paar in die HashMap, zählen die Anzahl der Zeiten, die die angegebenen Zeichen erscheint in der key(string) und erhöhen es durch den entsprechenden Wert in die HashMap.
Meine Frage ist: gibt es einen besseren Weg, dies zu tun?
Hier der code:
HINWEIS: BITTE LESEN SIE DIE GESAMTE ANTWORT AKZEPTIERT.
public static int findFreq(String[] arr,char c) {
Map<String,Integer> map = new HashMap<String,Integer>();
for(int i=0;i<arr.length;i++) {
if(map.containsKey(arr[i]))
map.put(arr[i],map.get(arr[i])+1);
else
map.put(arr[i], 1);
}
int freq=0;
for(Entry<String,Integer> entr:map.entrySet()) {
String s = entr.getKey();
for(int i=0;i<s.length();i++) {
if(s.charAt(i)==c)
freq += entr.getValue();
}
}
return freq;
}
- Zu sehen, wie Sie gehen, um zu schauen, jedes einzelne Zeichen in dem array zu lösen, wirst du nie besser als O(n). Ich sehe nicht, wie mache ich eine map von strings ist, all das hilfreich, (in der Tat brauchen Sie nicht die Karte, wenn Sie nie gehen, um zu schauen
arr
wieder). Wenn du ihn behalten willst, würd ich die Karte aus jedem Buchstaben im alphabet die Häufigkeit, mit der es Auftritt (d.h.,h --> 3
). - Berechnung des hashcode für einen string beinhaltet, an jeder Brief. Gewährt, dass der hashcode kann schon einmal berechnet (und daher zwischengespeichert), der zweite Ansatz ist potenziell erheblich mehr Arbeit und (im Durchschnitt) nicht weniger Arbeit. Es sind Einsparungen nur wenn die Zeichenfolge zählt, sind deutlich mehr als jeweils 1.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ansatz 2 ist nicht sehr optimiert, was sollten Sie wirklich tun ist, erstellen Sie eine
Map<Character,Integer>
du dann nicht die zweite Schleife zu zählen, aber Sie müssen in einer Schleife jedes Zeichen in jeder Zeichenfolge.Ansatz 1, je nach Ihrer Implementierung auch zählt nur für jeden vorkommenden Zeichen in der Zeichenfolge, hat es zu prüfen, ob das Zeichen zweimal vorkommt, z.B.
"hash"
?Entweder Ansatzes zu vergleichen JEDER Charakter in JEDER String und dann zählen
Dies ist, wie Ansatz 2 sollte
So oder so beide Ansätze werden O(n), aus der docs für HashMap
Aber, dass sagte, auch mit dem Ansatz, den ich oben angegeben dies erfordert zusätzliche
get
beim Auffüllen der Karte.Also Ansatz 1 ist besser, wenn die Verwendung für einen single Suche, wenn wiederholt, dann Ansatz 2 ist der Weg zu gehen (aber füllen Sie die Karte außerhalb der Methode)
Einige Metriken für Sie:
Ich mich zurückziehe, meine Methode, es erscheint deine Map Ansatz ist schneller!
Dies war meine array-Methode (bei Ihnen unterscheidet)
arr[i].toCharArray()
in meine Methode wäre wahrscheinlich, was Sie aufhältSorry, ich denke, dass Ansatz 2 Dinge verlangsamt. Um jede saite auf die
HashMap
die Methode berechnet den hash-code, der schaut auf jedes Zeichen in der Zeichenfolge. So einrichten dasHashMap
sieht schon auf jedes Zeichen in jeder Zeichenfolge, die dauert so lange, wie das, was Sie würde tun müssen, mit Ansatz 1, plus dann machen Sie einen anderen pass über die Karte.Ansatz 1 ist hier vorzuziehen. Die Kosten
O(N)
entweder von Ihnen im schlimmsten Fall. Der zweite Ansatz mitHashMap<String>
für die Erinnerung an alte besucht string (inhärente Vermischung Kosten) würde nicht zu einer Verbesserung führen, um Leistung verdient erwähnt zu werden. Wir sollten es vermeiden, vorzeitige Optimierung, wieapproach 1
ist einfacher.Nicht unbedingt.
Noch eine Möglichkeit wäre zu "glätten" das array in einen einzelnen string an und Suche für ein einzelnes Zeichen in es (fast das gleiche wie deine Variante 1). Dies würde vielleicht die Geschwindigkeit denkt, ein wenig, aber es wäre nicht unbedingt, dass der code "besser". Beispiel für ein char-Suche in einem string gefunden werden können in diesem SO beantworten.
Nein, du wirst nie besser als O(n) für eine einzige Suche. Aber wenn du gehst zu suchen, oft gegen den gleichen array, für verschiedene Charaktere, Sie können beginnen, durch laufen durch das array und Aufbau eine hash map, die aus einzelnen Zeichen, um die Anzahl der vorkommen. Dann, für jede Suche, die Sie gerade zu tun haben, eine einfache konstant-Zeit-look-up, nicht eine O(n) suchen.
Hashmap ist sogar langsamer als die erste. Beide algorithmen muss von jedem Charakter einmal, so dass beide braucht O(n) Zeit. Aber der erste ist viel einfacher und weniger code-Zeilen ausgeführt werden würde.
Netter Versuch, aber 🙂