295. Find Median from Data Stream

leetcode hard

#array#csharp#design#hard#leetcode#search#sort

Task

Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, то медианы нет, и медиана — это среднее арифметическое двух средних значений.

Например, для arr = [2, 3, 4] медиана равна 3.

Например, для arr = [2, 3] медиана равна (2 + 3) / 2 = 2.5.

Реализуйте класс MedianFinder:

MedianFinder() инициализирует объект MedianFinder.

void addNum(int num) добавляет целое число num из потока данных в структуру данных.

double findMedian() возвращает медиану всех элементов на данный момент. Ответы с точностью до 10^-5 от фактического ответа будут приниматься.

Пример:

Input

["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]

[[], [1], [2], [], [3], []]

Output

[null, null, null, 1.5, null, 2.0]

Explanation

MedianFinder medianFinder = new MedianFinder();

medianFinder.addNum(1); // arr = [1]

medianFinder.addNum(2); // arr = [1, 2]

medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)

medianFinder.addNum(3); // arr[1, 2, 3]

medianFinder.findMedian(); // return 2.0

C# solution

matched/original

using System;
using System.Collections.Generic;
public class MedianFinder {
    private List<int> numbers;
    public MedianFinder() {
        numbers = new List<int>();
    }
    public void AddNum(int num) {
        numbers.Add(num);
    }
    public double FindMedian() {
        numbers.Sort();
        int n = numbers.Count;
        if (n % 2 == 0) {
            return (numbers[n / 2 - 1] + numbers[n / 2]) / 2.0;
        } else {
            return numbers[n / 2];
        }
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class MedianFinder {
    private List<int> numbers;
    public MedianFinder() {
        numbers = new List<int>();
    }
    public void AddNum(int num) {
        numbers.push_back(num);
    }
    public double FindMedian() {
        numbers.Sort();
        int n = numbers.size();
        if (n % 2 == 0) {
            return (numbers[n / 2 - 1] + numbers[n / 2]) / 2.0;
        } else {
            return numbers[n / 2];
        }
    }
}

Java solution

matched/original

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class MedianFinder {
    private List<Integer> numbers;

    public MedianFinder() {
        numbers = new ArrayList<>();
    }

    public void addNum(int num) {
        numbers.add(num);
    }

    public double findMedian() {
        Collections.sort(numbers);
        int n = numbers.size();
        if (n % 2 == 0) {
            return (numbers.get(n / 2 - 1) + numbers.get(n / 2)) / 2.0;
        } else {
            return numbers.get(n / 2);
        }
    }
}

JavaScript solution

matched/original

class MedianFinder {
    constructor() {
        this.numbers = [];
    }

    addNum(num) {
        this.numbers.push(num);
    }

    findMedian() {
        this.numbers.sort((a, b) => a - b);
        const n = this.numbers.length;
        if (n % 2 === 0) {
            return (this.numbers[Math.floor(n / 2) - 1] + this.numbers[Math.floor(n / 2)]) / 2.0;
        } else {
            return this.numbers[Math.floor(n / 2)];
        }
    }
}

Python solution

matched/original

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

    def addNum(self, num: int) -> None:
        self.numbers.append(num)

    def findMedian(self) -> float:
        self.numbers.sort()
        n = len(self.numbers)
        if n % 2 == 0:
            return (self.numbers[n // 2 - 1] + self.numbers[n // 2]) / 2.0
        else:
            return float(self.numbers[n // 2])

Go solution

matched/original

package main

import (
    "sort"
)

type MedianFinder struct {
    numbers []int
}

func Constructor() MedianFinder {
    return MedianFinder{numbers: []int{}}
}

func (this *MedianFinder) AddNum(num int) {
    this.numbers = append(this.numbers, num)
}

func (this *MedianFinder) FindMedian() float64 {
    sort.Ints(this.numbers)
    n := len(this.numbers)
    if n%2 == 0 {
        return float64(this.numbers[n/2-1]+this.numbers[n/2]) / 2.0
    } else {
        return float64(this.numbers[n/2])
    }
}

Explanation

Algorithm

Храните числа в контейнере с возможностью изменения размера:

Создайте массив для хранения чисел.

Добавление нового числа:

Добавьте новое число в массив.

Вычисление и вывод медианы:

Отсортируйте массив.

Если размер массива нечетный, верните среднее значение массива.

Если размер массива четный, верните среднее арифметическое двух средних значений массива.

😎