Häufigste Zahl in einem Array < Java < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:27 Sa 03.05.2008 | | Autor: | wolle238 |
Moin,
ich bin grad auf der Suche nach einer einfachen Lösung für eine Methode, der ich ein INT Array übergebe und die mir dann die am häufigsten vorkommende Zahl zurückgibt. Ich kriegs nur hin wenn ich vorher das komplette Array sortiere aber es soll wohl auch mit wesentlich geringerem Aufwand möglich sein. Jemand einen Tipp für mich?
MfG
Wolle
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:47 Sa 10.05.2008 | | Autor: | bamm |
Hallo,
nur mal so als Idee ohne Sortieren(ob das wirklich schneller ist, müsste man halt mal eine Laufzeitabschätzung durchführen...): Du legst ein zweites Array an in dem die Häufigkeiten der Zahlen gespeichert werden und eine int Variable, in der der die aktuell am häufigsten vorkommende Zahl gespeichert wird (hier high genannt). Dann läufst du durch dein Eingabe Array durch und erhöhst jeweils in deinem zweiten Array den Eintrag für diese Zahl um 1, also z.B. haeuf[zahl] = haeuf[zahl] + 1. Dann vergleichst du noch ob der Wert von haeuf[zahl] > haeuf[high] ist. Falls ja, ersetzt du den Wert in high mit high = zahl. Das ganze erfordert dann für jede Zahl im Eingabearray einen Array Zugriff und einen Vergleich (und ggf. noch einen Ersetzungsschritt für high). Sollte also wenn ich mich nicht täusche in O(n) Zeit ablaufen.
|
|
|
|
