假设那个数组 arr 已按递增顺序排序，下面的代码填充数组 D ，每个 i , D[i] 是数值的中位数 (arr[0], ..., arr[i]) .

// uncomment line below if arr is not sorted
// Arrays.sort(arr);

for (int i = 0, i < arr.length; i++)
{
    if (i % 2 == 0) {

        // calculate median for array with odd length
        D[i] = arr[i/2];
    }
    else {

        // calculate median for array with even length
        D[i] = (arr[i/2] + arr[i/2 + 1]) / 2;
    }  
}

复杂度：上述算法的时间复杂度为o（n）。
如果初始数组没有排序，我们必须对它进行排序，这会增加时间复杂度o（nlogn）。最后的时间复杂度是o（nlogn+n）=o（nlogn）

Theta(n log n) 复杂性方法：
创建两个堆-最大堆和最小堆
遍历数组 a 并在两堆数据结构中插入每个元素。
如果元素大于currend median，则将其添加到最小堆（它包含较大的元素），否则将其添加到最大堆（包含较小的元素）
保持（几乎）大小相等的堆( (k+1)/2 以及 k/2 在第k步），如果需要，将顶部元素移动到另一个堆中。
当前切片的中间元素位于较大堆的顶部
我希望有这些线索就足够了。
java（我不得不学一点；）

public static void main (String[] args) throws java.lang.Exception
{  Integer[] arr= {10,70,4,15,20,12,8,17};
   PriorityQueue<Integer>maxheap = new PriorityQueue<>(10, Collections.reverseOrder());
   PriorityQueue<Integer>minheap = new PriorityQueue<>(10);
   Integer median = -9999;
   for (Integer a: arr) {
      if (a >= median) {
         minheap.add(a);
         if (minheap.size() - maxheap.size() >= 2)
             maxheap.add(minheap.poll());
      }
        else {
         maxheap.add(a);
         if (maxheap.size() - minheap.size() >= 2)
             minheap.add(maxheap.poll());
        } 
        Integer diff = maxheap.size() - minheap.size();
        if (diff == 1)
             median = maxheap.peek();
        else if (diff == -1)
           median = minheap.peek();
        else   
            median = Math.min(minheap.peek(), maxheap.peek());
        System.out.println(median);
   }
}

python实现（首先完成）。减号用于提供max heap（python）的正确顺序 heapq 是最小堆），没有额外的比较器。

import heapq

arr=[10,70,4,15,20,12,8,17]
print(arr)
d = []
ds = []
minheap = []
maxheap = []
median = -99999
for i in range(len(arr)):
    sli = arr[:i+1]
    sli.sort()
    ds.append(sli[(len(sli) - 1)//2])

    if arr[i] >= median:
        heapq.heappush(minheap, arr[i])
        if len(minheap) - len(maxheap) >= 2:
           heapq.heappush(maxheap, -heapq.heappop(minheap))
    else:
        heapq.heappush(maxheap, -arr[i])
        if len(maxheap) - len(minheap) >= 2:
           heapq.heappush(minheap, -heapq.heappop(maxheap))

    diff = len(maxheap) - len(minheap)
    if diff == 1:
        median = -maxheap[0]
    elif diff == -1:
        median = minheap[0]
    else:
        median = min(minheap[0], -maxheap[0])
    d.append(median)

print(ds) #dumb method to compare
print(d)

>>>[10, 10, 10, 10, 15, 12, 12, 12]
>>>[10, 10, 10, 10, 15, 12, 12, 12]