Сложность: hard
Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, то медианы нет, и медиана — это среднее арифметическое двух средних значений.
Например, для 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
👨💻 Алгоритм:
1⃣Храните числа в контейнере с возможностью изменения размера:
Создайте массив для хранения чисел.
2⃣Добавление нового числа:
Добавьте новое число в массив.
3⃣Вычисление и вывод медианы:
Отсортируйте массив.
Если размер массива нечетный, верните среднее значение массива.
Если размер массива четный, верните среднее арифметическое двух средних значений массива.
😎 Решение:
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)];
}
}
}Ставь 👍 и забирай 📚 Базу знаний