Problem
Sortiere die Werte in aufsteigender Reihenfolge. Bei einer ungeraden Anzahl von Werten nimm den mittleren Wert. Bei einer geraden Anzahl berechne das arithmetische Mittel der beiden mittleren Werte. Diese Aufgabe akzeptiert nur nicht-leere Listen.
Implementiere median_number(numbers).
Eingabe
numbers: Die nicht-leere Liste von Werten.
Ausgabe
Gib die Medianzahl als Zahl zurück; sie kann auf .5 enden.
Einschränkungen
1 ≤ Listenlänge ≤ 100.000. Jeder Wert ist eine ganze Zahl zwischen −1.000.000.000 und 1.000.000.000.
Beispiele
Eingabe:
numbers = [2, 8, 4, 10]
Erwartete Ausgabe:
expected = 6.0Eingabe:
std::vector<long long> numbers = {2, 8, 4, 10};
Erwartete Ausgabe:
double expected = 6.0;Eingabe:
long[] numbers = new long[] {2, 8, 4, 10};
Erwartete Ausgabe:
double expected = 6.0;Erläuterung
Sortierte Reihenfolge ist 2, 4, 8, 10. Das mittlere Paar ergibt im Durchschnitt (4 + 8) / 2 = 6.
Eingabe:
numbers = [9, 1, 4]
Erwartete Ausgabe:
expected = 4.0Eingabe:
std::vector<long long> numbers = {9, 1, 4};
Erwartete Ausgabe:
double expected = 4.0;Eingabe:
long[] numbers = new long[] {9, 1, 4};
Erwartete Ausgabe:
double expected = 4.0;Erläuterung
Sortierte Reihenfolge ist 1, 4, 9, wobei der mittlere Wert 4 ist.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Das Median hängt von der sortierten Reihenfolge ab, also zählen die Positionen in der sortierten Liste.
Hinweis 2
Nach dem Sortieren nimm bei ungerader Länge das mittlere Element, bei gerader Länge die beiden mittleren.
Hinweis 3
Achte darauf, beim Mittelwert die beiden Hälften zu behalten, denn das Ergebnis kann auf .5 enden.
Erwartete Komplexität
Zeit O(n log n), zusätzlicher Speicher O(n)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.