Problème
Triez les valeurs par ordre croissant. Pour un nombre impair de valeurs, prenez celle du milieu. Pour un nombre pair, prenez la moyenne arithmétique des deux valeurs centrales. Ce défi n'accepte que des listes non vides.
Implémentez median_number(numbers).
Entrée
numbers : La liste non vide de valeurs.
Sortie
Retournez la médiane sous forme de nombre ; elle peut se terminer par .5.
Contraintes
1 ≤ longueur de la liste ≤ 100 000. Chaque valeur est un entier compris entre −1 000 000 000 et 1 000 000 000.
Exemples
Entrée :
numbers = [2, 8, 4, 10]
Sortie attendue :
expected = 6.0Entrée :
std::vector<long long> numbers = {2, 8, 4, 10};
Sortie attendue :
double expected = 6.0;Entrée :
long[] numbers = new long[] {2, 8, 4, 10};
Sortie attendue :
double expected = 6.0;Explication
L'ordre trié est 2, 4, 8, 10. Le couple central donne une moyenne de (4 + 8) / 2 = 6.
Entrée :
numbers = [9, 1, 4]
Sortie attendue :
expected = 4.0Entrée :
std::vector<long long> numbers = {9, 1, 4};
Sortie attendue :
double expected = 4.0;Entrée :
long[] numbers = new long[] {9, 1, 4};
Sortie attendue :
double expected = 4.0;Explication
L'ordre trié est 1, 4, 9, dont la valeur centrale est 4.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
La médiane dépend de l’ordre trié, donc ce sont les positions dans la liste triée qui comptent.
Indice 2
Après tri, prends l’élément du milieu pour une longueur impaire, ou combine les deux éléments centraux pour une longueur paire.
Indice 3
Fais attention à conserver les décimales quand tu fais la moyenne de deux valeurs centrales, car le résultat peut finir en .5.
Complexité attendue
temps O(n log n), espace supplémentaire O(n)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.