Find Median from Data Stream

Q: Quelle est la complexité temporelle de Find Median from Data Stream ?

Avec deux tas, addNum est en O(log n) , avec au plus trois insertions ou suppressions dans les tas, et findMedian est en O(1) , avec deux lectures. Chaque valeur est stockée, donc l’espace requis est en O(n) . Trier à chaque requête coûte plutôt O(n log n) par appel à findMedian .

Q: Pourquoi ne pas conserver les valeurs dans un tableau trié ?

Un tableau trié permet de trouver la médiane en O(1) avec findMedian , et la recherche binaire trouve où insérer une nouvelle valeur en O(log n) . Mais son insertion décale toutes les valeurs après ce point, soit O(n) par addNum .

DifficileTas

+10

Conçois une structure dotée de deux opérations : addNum stocke un entier, et findMedian renvoie la médiane de toutes les valeurs stockées jusqu'à présent. Pour un nombre impair de valeurs, la médiane est la valeur du milieu ; pour un nombre pair, c'est la moyenne des deux valeurs du milieu.

L'opération i est ops[i], et values[i] contient le nombre pour une opération addNum et 0 pour une opération findMedian. Exécute-les dans l'ordre sur une structure vide et renvoie une chaîne pour chaque opération : "null" pour addNum, la médiane pour findMedian. Écris la médiane sous la forme "3", "2.5" ou "-0.5" : sans point décimal pour un nombre entier, et zéro sous la forme "0", jamais "-0".

Fonction

medianStreamOps(ops: string-array, values: integer-array) → string-array

opsstring-array: les opérations, dans l’ordre où elles sont exécutées
valuesinteger-array: le nombre pour chaque addNum, 0 pour chaque findMedian
Renvoiestring-array: une réponse par opération, sous forme de texte

Contraintes

1 ≤ ops.length ≤ 3000
values.length == ops.length
Chaque ops[i] est addNum ou findMedian.
-10⁵ ≤ values[i] ≤ 10⁵ pour addNum, et values[i] == 0 pour findMedian.
findMedian est appelé uniquement après au moins un addNum.

Exemples

Entrée: ops = ["addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"]values = [5, 0, 1, 0, 8, 0, 3, 0]
Sortie: ["null", "5", "null", "3", "null", "5", "null", "4"]
Explication: Avec 1 et 5, la médiane est (1 + 5) / 2 = 3. Avec 1, 5 et 8, elle est 5, et avec 1, 3, 5 et 8, elle est (3 + 5) / 2 = 4.

Pour aller plus loin

Si chaque valeur était comprise entre 0 et 100, comment pourrais-tu faire en sorte que les deux opérations s’exécutent en temps constant ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

La médiane se situe entre les deux moitiés des données, donc l’ordre à l’intérieur de chaque moitié n’a pas d’importance : seuls comptent la plus grande valeur de la moitié inférieure et la plus petite de la moitié supérieure. Deux tas gardent précisément ces deux valeurs au sommet. Chaque addNum coûte O(log n) et chaque findMedian lit les deux sommets en O(1).

Trier à chaque appel de findMedian

Intuition

Stockez chaque valeur dans une liste. findMedian la trie et lit les indices (total-1)/2 et total/2, avec une division entière : le même indice pour un nombre impair, la paire centrale pour un nombre pair. Additionnez les deux valeurs et divisez la somme par deux : vous obtenez ainsi la médiane dans les deux cas.

Divisez par deux avec des entiers. Une somme paire se divise exactement. Une somme impaire devient la moitié de sa valeur absolue suivie de .5, avec le signe de la somme : -3 devient -1.5.

Chaque requête effectue un nouveau tri. Avec 1,500 ajouts et une requête après chacun d’eux, cela représente environ 10^7 comparaisons, alors que les tas ne nécessitent que quelques dizaines de milliers d’étapes.

Algorithme

Conservez une liste values.
Pour addNum x, ajoutez x et enregistrez "null".
Pour findMedian, triez values et additionnez values[(total-1)/2] et values[total/2].
Divisez la somme par deux sous forme de texte avec des entiers et enregistrez-la.

def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


class MedianFinder:
    def __init__(self):
        self.values = []

    def addNum(self, x):
        self.values.append(x)

    def findMedian(self):
        self.values.sort()
        total = len(self.values)
        # For an odd count both indexes point at the one middle value.
        return half_text(self.values[(total - 1) // 2] + self.values[total // 2])


def medianStreamOps(ops, values):
    finder = MedianFinder()
    result = []
    for op, x in zip(ops, values):
        if op == "addNum":
            finder.addNum(x)
            result.append("null")
        else:
            result.append(finder.findMedian())
    return result

Deux tas séparés par la médiane

Intuition

Répartissez les valeurs entre une moitié inférieure low et une moitié supérieure high, de sorte que chaque valeur de low soit inférieure ou égale à chaque valeur de high, et que low soit de la même taille que high ou comporte un élément de plus. La médiane est la plus grande valeur de low ou, si le nombre de valeurs est pair, la moyenne de cette valeur et de la plus petite valeur de high. Un tas max pour low et un tas min pour high permettent de garder ces valeurs au sommet.

Une nouvelle valeur est ajoutée à low si elle est inférieure ou égale à la valeur au sommet de low, sinon à high. Lorsque les tailles s'écartent, déplacez un élément du sommet de l'un vers l'autre : c'est la valeur la plus proche de l'autre moitié, ce qui préserve l'ordre. Un ajout nécessite quelques opérations sur le tas, soit O(log n), ou O(n) en R, qui copie le tas à chaque modification.

Après les quatre ajouts du premier exemple, low contient 3 et 1, et high contient 5 et 8.

Algorithme

Conserve un tas max low pour la moitié inférieure et un tas min high pour la moitié supérieure.
addNum x : ajoute x à low si low est vide ou si x est inférieur ou égal à son sommet ; sinon, ajoute-le à high.
Si low contient deux valeurs de plus que high, déplace le sommet de low vers high. Si high contient plus de valeurs que low, déplace le sommet de high vers low.
findMedian : si low est plus grand, note son sommet. Sinon, additionne les deux sommets et divise la somme par deux avec des entiers.

import heapq


def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


class MedianFinder:
    def __init__(self):
        self.low = []   # the smaller half; heapq is a min-heap, so it stores -x to keep the largest on top
        self.high = []  # the larger half, smallest on top

    def addNum(self, x):
        if not self.low or x <= -self.low[0]:
            heapq.heappush(self.low, -x)
        else:
            heapq.heappush(self.high, x)
        # Rebalance: low holds as many values as high, or one more.
        if len(self.low) > len(self.high) + 1:
            heapq.heappush(self.high, -heapq.heappop(self.low))
        elif len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def findMedian(self):
        if len(self.low) > len(self.high):
            return str(-self.low[0])
        return half_text(-self.low[0] + self.high[0])


def medianStreamOps(ops, values):
    finder = MedianFinder()
    result = []
    for op, x in zip(ops, values):
        if op == "addNum":
            finder.addNum(x)
            result.append("null")
        else:
            result.append(finder.findMedian())
    return result

Pièges et cas limites

Choisir le tas en fonction de sa taille plutôt que de sa valeur. Insérer dans le plus petit tas sans comparer rompt l’ordre entre les deux moitiés, et les racines ne correspondent plus aux valeurs du milieu.
Diviser par deux avec une division entière classique. En C et en Java, -1 / 2 vaut 0, donc ajouter .5 affiche 0.5 pour -0.5. En Python, -3 // 2 vaut -2, ce qui affiche -2.5 pour -1.5. En virgule flottante, certaines langues affichent 3.0 ou 2.500000.
Stocker low en le niant dans un tas min et oublier de le nier à nouveau en lisant sa racine ou en déplaçant une valeur vers high.
Écrire -0. Les valeurs du milieu -1 et 1 ont une somme de 0, et la réponse est "0".

Questions fréquentes3

Quelle est la complexité temporelle de Find Median from Data Stream ?

Avec deux tas, addNum est en O(log n), avec au plus trois insertions ou suppressions dans les tas, et findMedian est en O(1), avec deux lectures. Chaque valeur est stockée, donc l’espace requis est en O(n). Trier à chaque requête coûte plutôt O(n log n) par appel à findMedian.

Pourquoi ne pas conserver les valeurs dans un tableau trié ?

Un tableau trié permet de trouver la médiane en O(1) avec findMedian, et la recherche binaire trouve où insérer une nouvelle valeur en O(log n). Mais son insertion décale toutes les valeurs après ce point, soit O(n) par addNum.

Peux-tu trouver la médiane exacte d’un flux sans stocker chaque valeur ?

Pas en général. Toute valeur observée jusqu’ici peut devenir la médiane plus tard, selon ce qui arrive ensuite ; il faut donc toutes ces valeurs pour obtenir une réponse exacte.

def medianStreamOps(ops, values):
    # Écrivez le code ici

Test #1

Test #2

Arguments

ops = ["addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"]
values = [5, 0, 1, 0, 8, 0, 3, 0]

Résultat attendu

["null", "5", "null", "3", "null", "5", "null", "4"]