小编Hri*_*iev的帖子

我最近在求职面试中遇到的一个问题是:

Write a data structure that supports two operations.
1. Adding a number to the structure.
2. Calculating the median.
The operations to add a number and calculate the median must have a minimum time complexity.

我的实现非常简单,基本上保持元素排序,这样添加元素成本O(log(n))而不是O(1),但中位数是O(1)而不是O(n*log(n) )

我还添加了一个天真的实现,但包含numpy数组中的元素:

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from random import randint, random
import math
from time import time

class MedianList():
    def __init__(self, initial_values = []):
        self.values = sorted(initial_values)
        self.size = len(initial_values)

    def add_element(self, element):
        index = …