# Häufigstes Zeichen in einem Char-Array ermitteln?



## 0001001 (28. Feb 2006)

Kann mir jemand einen Tip geben wie man am einfachsten das häufigste Zeichen eines Char-Array ermittelt?

Ich hätte es jetzt so gemacht:

```
public static int getk(char[] a){
		int laenge= a.length;
		int[] array = new int[laenge];	// neues array anlegen für die häufigkeit der einzelnen buchstaben
		for(int i=0;i<=a.length-1;i++){
			for(int j=0;j<=a.length-1;j++){
				if(a[i]==a[j]){
					array[i]= array[i] +1;		// wenn ein buchstabe mehrmals auftritt fuer jeden auftritt eins addieren
				}
			}
		}
}
```

Es wird ein zweites array (array) angelegt in dem für jeden buchstaben aus dem char array a die häufigkeit gespeichert werden soll.
Jetzt wird mit einer doppelschleife jeweils ein element mit allen anderen verglichen und falls es gleich ist wird im array eins dazugezählt.
Jetzt muss man das array array nochmals durchlaufen und den größten wert ermitteln.

Geht das auch einfacher?


----------



## Leroy42 (28. Feb 2006)

Wenn dur nur *den* häufigsten Buchstaben brauchst und nicht die Häufigkeiten aller
Buchstaben, kannst du den Code beschleunigen; aber nicht vereinfachen. Zur Zeit gehst
du die mehrfachen Elemente auch mehrfach durch   Aufwand: O(n^2)

1. Dein zweites Array ist nur ein char-Array. Es nimmt die Buchstaben auf, die schon
    getestet wurden; nebenbei merkst du dir wieviele verschiedene Buchstaben du in
    dieses Array bereits aufgenommen hast.
2. Du merkst dir das aktuell häufigste Zeichen und wie oft es vorkommt.
3. Eine Schleife über dein Ursprungsarray. Wenn das aktuelle Zeichen *noch nicht*
    bearbeitet wurde (kein Eintrag im 2. Array bis zu dessen aktueller Länge) dann
4. Eine innere Schleife, beginnend ab dem i+1. Index deiner äußeren bis zum Ende,
    zählt die Vorkommen des aktuellen Zeichens
5. Falls neues Maximum ==> merken.

Aufwand: Kleiner als O(n*(n-1)/2)

Wenn der Bereich deines char-Arrays allerdings bekannt ist und _relativ klein_, dann ist
die schnellste Möglichkeit ein 2. Array das dein char-Bereich abdeckt und indem du _direkt_,
d.h. mit nur einem Zugriff die Anzahl mitzählst. Am Schluß in diesem Array das größte
Element suchen.
Aufwand: O(n)

Da char's _nur_ Werte von 0..65535 annehmen können, ist diese Methode heutzutage
immer vorzuziehen. Oder hast du eine Java-Installation auf deinem alten C64


----------



## 0001001 (28. Feb 2006)

Hehe, ne mein C64 sammelt Staub im Keller =)

Ich brauche nur *den* häufigsten Buchstaben, wenn es allerdings häufigste Buchstaben gibt, brauch ich die natürlich alle.

Du schreibst das so leicht, dass man beim Schleifendurchlauf gleich mitzählt, wie oft ein Buchstabe vorkommt, leider verstehe ich dich nicht ganz.
Meinst du mit char-Bereich abdecken, dass wenn mein char array 500 Buchstaben hat, ich dann auch ein int array mit 500 Feldern anlege?
Oder meinst du, dass z.B. nur Buchstaben des Alphabets vorkommen und ich dann ein int array anlege mit 26 Feldern?
Bei letzterem müsste ich doch für jeden Buchstaben einen solchen Vergleich machen:

```
if (char_array[i]== 'A')
                int_array[i] = int_array[i] +1;
```
Und das für alle 26 Buchstaben.


----------



## Leroy42 (28. Feb 2006)

0001001 hat gesagt.:
			
		

> Oder meinst du, dass z.B. nur Buchstaben des Alphabets vorkommen und ich dann ein int array anlege mit 26 Feldern?


Genau!
Aber dieses Häufigkeitsarray inidzierst du dann _direkt _ mit deinem, eventuell
transformierten, char. Mal am Beispiel der Buchstaben.

Wenn du weißt, daß du nur (ASCII) Großbuchstaben hast, brauchst dein array nur 26
Elemente groß sein und du benutzt folgende Transformation:

'A' ==> Index 0
'B' ==> Index 1
...
'Z' ==> Index 25

Also

```
int[] count = new int['Z'-'A'+1];     // weiß jetzt nicht ob lokale arrays schon mit 0 initialisiert sind.
for (int i=0; i < charArray.length)
    count[charArray[i] - 'A']++;
max = 0;
for (int i=0; i < count.length)
    if (count[i] > count[max]) max = i
// Jetzt ist (char) (max+'A') das häufigst zeichen mit anzahl count[max]
```
Hierbei muß der mögliche Zeichenbereich allerdings zusammenhängend sein.

Aber, wie schon gesagt, bei heutigen Rechnern kannst du getrost den gesamten
char-Bereich benutzen. Und der Durchlauf durche die 64K-Elemente am Ende zur
Bestimmung des häufigsten Zeichens dauert auf meinem Rechner z.B. nur
187 Nanosekunden.


----------



## 0001001 (28. Feb 2006)

Danke das hilft mir schon sehr. Habs zwischenzeitlich mal so probiert:
Hier sind jetzt pro Buchstabe die Häufigkeiten im Array gespeichert:

```
public static int getk(char[] a){	

		*/
		char[] alphabet = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
		int[] alphabetnummerisch = new int[26];
		for(int w=0;w<=a.length-1;w++){
			for(int v=0;v<=alphabet.length-1;v++){
				if(a[w]==alphabet[v]){
					alphabetnummerisch[v]++;
				}					
			}				
		}
```


----------



## Leroy42 (28. Feb 2006)

Im Prinzip richtig, aber dein zweites char-Array und die gesamte innere
Schleife in der du den Index für dein aktuelles Zeichen suchst sind
schlicht und ergreifend unnötig. :bahnhof: 

Zur Verdeutlichung:

Wo findet deine innere Schleife den Index für das Zeichen 'A': *Immer* an der Stelle 0, also index=0.
Wo findet deine innere Schleife den Index für das Zeichen 'B': *Immer* an der Stelle 1, also index=1.
Wo findet deine innere Schleife den Index für das Zeichen 'Z': *Immer* an der Stelle 25, also index=25.

Verstehst du was ich meine  ???:L 

Du brauchst gar nicht lange zu suchen, sondern kannst mit *einer Subtraktion* sofort den Index benennen.

'A' - 'A' = 0
'B' - 'A' = 1
'Z' - 'A' = 25

Also einfach:


```
for(int v = 0;v < alphabet.length;v++) { 
    alphabetnummerisch[a[w] - 'A']++; 
}
```
Klar?


----------



## Gast (28. Feb 2006)

hehe ja danke dir!


----------

