Let Code Day70 À partir de zéro "295. Trouver la médiane à partir du flux de données"

Aperçu

Il semble que des tests de codage soient menés à l'étranger lors d'entretiens d'ingénieurs, et dans de nombreux cas, l'essentiel est d'implémenter des fonctions et des classes spécifiques en fonction du thème.

Apparemment, de nombreux ingénieurs prennent des mesures sur le site appelé LetCode.

C'est un site qui forme la puissance algorithmique qui peut résister au test de codage effectué au début de l'histoire, et c'est une voie inévitable pour ceux qui veulent faire carrière dans une entreprise de technologie à l'étranger.

Je l'ai écrit en grand, mais je n'ai pas l'intention d'avoir une telle interview pour le moment.

Cependant, en tant qu'ingénieur informatique, il serait préférable d'avoir le même niveau de puissance d'algorithme qu'un être humain, donc j'aimerais résoudre le problème de manière irrégulière et écrire la méthode que je pensais à l'époque sous forme de mémo.

Leetcode

Je le résolve avec Python3.

Table de codes Leet commençant à zéro

Dernière fois Leet Code Day69 "279. Perfect Squares" à partir de zéro

À l'heure actuelle, je donne la priorité au moyen des 100 questions les plus appréciées. Easy a été résolu, donc si vous êtes intéressé, veuillez vous rendre à la table.

Twitter Je le fais.

** Blog technique Commencé! !! ** ** Je pense que la technologie écrira sur LetCode, Django, Nuxt, etc. ** C'est plus rapide à mettre à jour **, merci pour votre coopération!

problème

295. Find Median from Data Stream

Le niveau de difficulté est difficile. Extrait des 100 questions les plus appréciées.

Le problème est l'implémentation de la classe.

La valeur médiane est la valeur médiane d'une liste ordonnée d'entiers. Si la taille de la liste est paire, il n'y a pas de valeurs intermédiaires. Par conséquent, la valeur médiane est la moyenne des deux valeurs intermédiaires.

Par exemple [2,3,4] La médiane est de 3

[2,3] La médiane est (2 + 3) / 2 = 2,5

Concevez une structure de données qui prend en charge les deux opérations suivantes:

void addNum (int num) - Ajoute une valeur entière du flux de données à la structure de données. double findMedian () - Renvoie la valeur médiane de tous les éléments précédents.

Example:

addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2

Solution

En gardant à l'esprit qu'il s'agit de la valeur médiane et non de la valeur moyenne, la manière de mettre en œuvre cette partie semble être une partie très importante.

L'autre partie ne semble pas difficile pour quiconque souhaite résoudre ce problème.

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.sorted_list = []
        self.length = 0
        

    def addNum(self, num: int) -> None:
        low,high = 0,self.length-1
        while high >= low:
            mid = (high+low)//2
            if self.sorted_list[mid] > num:
                high = mid-1
            else:
                low = mid+1
        self.sorted_list.insert(low,num)
        self.length += 1
        

    def findMedian(self) -> float:
        if self.length % 2 == 0:
            median = self.length//2
            return (self.sorted_list[median]+self.sorted_list[median-1])/2.0
        else:
            return self.sorted_list[self.length//2]


# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()
# Runtime: 296 ms, faster than 30.86% of Python3 online submissions for Find Median from Data Stream.
# Memory Usage: 25.2 MB, less than 18.26% of Python3 online submissions for Find Median from Data Stream.

En utilisant une dichotomie dans la partie ʻaddNumet en sauvegardant la longueur de la liste, j'ai décidé d'écrire en douceur en utilisant cette longueur dans lefindMedian`. Avec le recul, cela ressemble à un ensemble de choses de base.

Vous pouvez l'écrire si vous vous souvenez fermement de chaque élément de connaissance, mais c'est un type qui tombe dans le dilemme que la vitesse ne sort pas tellement. En ce qui concerne la façon d'améliorer à partir d'ici, vous pouvez voir à partir de l'exemple de réponse suivant que la partie de la dichotomie est devenue un peu plus lourde.

from heapq import *

class MedianFinder:

    def __init__(self):
        self.heaps = [], []

    def addNum(self, num):
        small, large = self.heaps
        heappush(small, -heappushpop(large, num))
        if len(large) < len(small):
            heappush(large, -heappop(small))

    def findMedian(self):
        small, large = self.heaps
        if len(large) > len(small):
            return float(large[0])
        return (large[0] - small[0]) / 2.0
# Runtime: 200 ms, faster than 82.39% of Python3 online submissions for Find Median from Data Stream.
# Memory Usage: 24.6 MB, less than 98.20% of Python3 online submissions for Find Median from Data Stream.

https://leetcode.com/problems/find-median-from-data-stream/discuss/74044/Very-Short-O(log-n)-%2B-O(1)

Vous avez fait deux listes et traité chacune comme un tas pour réduire le poids.

J'aurais aimé pouvoir convertir la réponse précédente comme celle-ci, mais cette fois, je l'ai retirée de la discussion parce que je ne comprenais pas.

Alors c'est tout pour cette fois. Je vous remercie pour votre travail acharné.