连续查找数字流中位数的最有效方法（在Python中）？

Question

我正在尝试解决一个问题，内容如下：

一队热切的个位数（您的输入）正在等待进入一个空房间。

我每分钟允许一位数字（从左边开始）进入房间。

每次有新的数字进入房间时，我都会在黑板上记下当前房间中所有数字的中位数。【中位数是按数字从小到大排列时位于中间的数字。】如果有两个中位数（即两个中间数），那么我不使用平均值，而是记下两者中较低的一个。

我把新的数字写在现有数字的右边，这样我的黑板上的数字就会变得越来越长。

当所有数字都进入房间后，黑板上会出现什么数字？

考虑示例输入：21423814127333

• 2（最左边的）被允许进入房间，它是唯一的数字，所以我在黑板上写下 2。
• 然后 1 被允许进入房间加入 2。这两个中较小的一个被用作中位数，所以我在黑板上将 1 写在 2 的右侧（我的数字现在是 21）
• 4现在进入房间。1、2 和 4 的中位数是 2，所以我在黑板上添加 2（我的数字现在是 212）
• ...这个过程一直持续到最后 3 个进入房间...所有数字现在都在房间里，排序后，它们是 1,1,1,2,2,2,3,3,3,3， 4,7,8,8。中位数字有两个，但都是 3，所以我在黑板上加了 3，最终的数字是 21222222222233

我当前的解决方案：

num = input()
new = str(num[0])
whole = [num[0]]

for i in range(1, len(num)):
    whole.append(num[i])
    whole.sort()
    new += whole[i//2]

print(new)

问题是它花费的时间太长 - 因此它通过了 6/10（隐藏）测试用例，但超出了其他 4 个测试用例的时间限制。任何帮助将不胜感激。

Answer 1

你重复排序，用键比较，所以总成本是O(N * N log N)，也就是说，它至少是二次的。

个位数（您的输入）正在等待输入

这个问题的关键是输入的范围限制。我们知道每个输入都x在这个范围内：

0 <= x < 10

使用计数器。我们可以轻松分配其中十个。

记录已进入房间的总位数。每次您必须报告中位数时，请计算 有序计数器的总和 ，当达到总计数的一半时停止。

max_val = 10
counter = {i: 0  for i in range(max_val)}
...
assert 0 <= input_val < max_val

counter[input_val] += 1

cum_sum = 0
for i in range(max_val):
    cum_sum += counter[i]
    ...

由于中位数是一项稳健的统计数据，因此您报告的中位数通常会具有一定的稳定性，例如“2, 1, 2, 2, 2, 2”。您可以通过增量计算累积和来进一步加快计算速度。不过，它不会改变大哦的复杂性，因为计数器的数量是恒定的。我们仍在考虑 O(N)，因为我们必须检查进入房间的 N 个数字中的每一个，然后报告当前的中位数。这确实击败了依赖平分有序向量的方法的 O(N log N) 成本。