Häufigstes Zeichen in einem Char-Array ermitteln?

[0001001]

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]

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]

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]

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]

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]

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]

hehe ja danke dir!