我在一次采访中遇到了一个有趣的算法问题。我给出了答案，但不确定是否有更好的主意。因此，我欢迎大家就他/她的想法写点东西。

您有一个空集。现在，将元素逐一放入集合中。我们假设所有元素都是整数，并且它们是不同的（根据set的定义，我们不考虑两个具有相同值的元素）。

每次将新元素添加到集合中时，都会询问集合的中值。中值的定义与数学中的定义相同：排序列表中的中间元素。这里，特别地，当集合的大小为偶数时，假设集合的大小= 2 * x，则中值元素是集合的第x个元素。

示例：从一个空集开始，当添加12时，中位数是12，当添加7时，中位数是7，当添加8时，中位数是8，当添加11时，中位数是8，加5时，中位数为8，当加16时，中位数为8，…

注意，首先，添加元素以一个接一个地设置，然后我们不知道要添加的元素。

我的答案。

由于这是有关查找中位数的问题，因此需要进行排序。最简单的解决方案是使用普通数组并保持数组排序。当出现新元素时，使用二进制搜索找到元素（log_n）的位置，并将该元素添加到数组中。由于它是普通数组，因此需要移动数组的其余部分，其时间复杂度为n。插入元素后，我们可以立即使用实例时间获取中值。

最差的时间复杂度是：log_n + n + 1。

另一种解决方案是使用链接列表。使用链接列表的原因是为了消除移动阵列的需要。但是找到新元素的位置需要线性搜索。添加元素需要立即花费时间，然后我们需要遍历数组的一半来找到中位数，该数组总是花费n
/ 2时间。

最差的时间复杂度是：n + 1 + n / 2。

第三种解决方案是使用二进制搜索树。使用树，我们避免移位数组。但是，使用二叉搜索树查找中位数并不是很有吸引力。因此，我改变二进制搜索树的方式总是使左子树和右子树保持平衡。这意味着在任何时候，左子树和右子树的节点数相同，或者右子树的节点数比左子树多。换句话说，确保根元素在任何时候都是中位数。当然，这需要更改树的构建方式。技术细节类似于旋转红黑树。

如果树得到正确维护，则可以确保最差时间复杂度为O（n）。

因此，这三种算法都与集合的大小线性相关。如果不存在亚线性算法，则可以将这三种算法视为最优解。由于它们彼此之间的差异不大，因此最好的方法是最容易实现，第二个方法是使用链接列表。

因此，我真正想知道的是，是否将有一个用于此问题的亚线性算法，如果是，它将是什么样子。有想法吗？

史蒂夫。