Wie berechnet man den Median eines MapInt, Int?

Question

Wie berechnet man den Median eines MapInt, Int?

8

Wie würde eine Implementierung eines Algorithmus in Java aussehen, um den Median zu berechnen?

Für eine Karte, wo der Schlüssel eine Nummer einer Sequenz darstellt und der Wert wie oft diese Zahl in der Sequenz erschien

Zum Beispiel:

%Vor%

in einer Karte:

%Vor%

würde ergeben:

%Vor%

Also, was ich suche, ist eine Java-Implementierung von calculateMedian .

algorithm java median

Chris 16.06.2010, 11:47

quelle

4 Antworten

Tags und Links algorithm java median

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Offizielle C ++ - Sprachuntergruppen

score 4 · Answer 1

Guava :

%Vor%

Nun ist die Antwort auf Ihre Frage:

%Vor%

Wirklich. Das ist es. (Oder überprüfen Sie, ob die Größe gerade ist und mitteln Sie die zwei zentralen Werte, um genau zu sein.)

Wenn die Anzahl besonders groß ist, wäre es schneller, das entrySet des Multisets zu verwenden und eine laufende Summe zu behalten, aber der einfachste Weg ist normalerweise gut.

score 3 · Answer 2

Lineare Zeit

Wenn Sie die Gesamtzahl der Zahlen kennen (in Ihrem Fall ist es 16), können Sie vom Anfang oder vom Ende der Karte gehen und die Zählungen aufsummieren, bis Sie zum runden (n / 2) ten Element kommen, oder für den Fall, dass die Summe sogar im Durchschnitt von Boden (n / 2) th und ceil (n / 2) th Elementen = Median .

Wenn Sie die Gesamtzählung nicht kennen, müssen Sie sie mindestens einmal durchlaufen.

Sublineare Zeit

Wenn Sie sich für die Datenstruktur entscheiden und eine Vorverarbeitung vornehmen können, sehen Sie sich die Wikipedia auf Auswahlalgorithmus an sogar ein sublinearer Algorithmus. Sie können die sublineare Zeit auch erhalten, wenn Sie etwas über die Verteilung der Daten wissen.

BEARBEITEN: Also unter der Annahme, dass wir eine Sequenz mit Zählungen haben, was wir tun können, ist

Beim Einfügen der Paare key -> count wird eine andere Karte beibehalten - key -> running_total
Auf diese Weise haben Sie eine Struktur, in der Sie total_count erhalten können, indem Sie sich die letzte Taste running_total
und können Sie eine binäre Suche durchführen, um das Element zu finden, bei dem die laufende Summe in der Nähe von total_count / 2

Dies verdoppelt die Speicherbelegung, ergibt aber O (log n) für Median und O (1) für total_count.

score 2 · Answer 3

Verwenden Sie SortedMap , d. h. a TreeMap
Iterieren Sie einmal durch die Karte, um die Gesamtzahl der Elemente zu berechnen, d. h. die Summe aller Vorkommen
Iterate erneut und addiere Vorkommen, bis du die Hälfte erreicht hast. Die Zahl, die dazu geführt hat, dass die Summe die Hälfte der Summe übersteigt, ist der Median
Testen Sie ausgiebig auf einzelne Fehler

score 1 · Answer 4

Für einen einfachen aber vielleicht nicht so effizienten Algorithmus würde ich es so machen:

1. Erweitern Sie die Karte zu einer Liste.

praktisch gesprochen: Iterieren Sie die Karte und fügen Sie der neuen Liste den Schlüssel 'value-times' hinzu. Zum Schluss die Liste sortieren.

%Vor%

2. Berechne den Median

Jetzt müssen Sie eine Methode int calculateMedian(List<Integer> sorted) implementieren. Dies hängt von der Art des Median ab, den Sie benötigen. Wenn es sich nur um den Stichprobenmedian handelt, ist das Ergebnis entweder der mittlere Wert (für Listen mit einer ungeraden Anzahl von Elementen) oder der Durchschnitt der beiden mittleren Werte (für Listen mit einer geraden Länge). Beachten Sie, dass die Liste sortiert werden muss!

(Ref: Sample Median / wikipedia )

OK, OK, obwohl Chris die Effizienz nicht erwähnt hat, hier ist eine Idee, wie man den Stichprobenmittelwert (!) berechnet, ohne die Karte zu erweitern ...

%Vor%

(Ich habe keinen Compiler zur Hand - wenn es zu viele Syntaxfehler hat, behandle es bitte als Pseudocode;))