在常数时间内找到均值和中位数

Question

这是一个常见的面试问题。您会接收到一串数字（假设超过一百万个），这些数字介于[0-999]之间。

Implement a class which supports three methods in O(1) 

* insert(int i); 
* getMean(); 
* getMedian(); 

这是我的代码。

public class FindAverage {

  private int[] store;
  private long size;
  private long total;
  private int highestIndex;
  private int lowestIndex;

  public FindAverage() {
    store  = new int[1000];
    size = 0;
    total = 0;
    highestIndex = Integer.MIN_VALUE;
    lowestIndex = Integer.MAX_VALUE;

  }

  public void insert(int item) throws OutOfRangeException {
    if(item < 0 || item > 999){
      throw new OutOfRangeException();
    }
    store[item] ++;
    size ++;
    total += item;
    highestIndex = Integer.max(highestIndex, item);
    lowestIndex = Integer.min(lowestIndex, item);
  }

  public float getMean(){
    return (float)total/size;
  }

  public float getMedian(){

  }
}

我似乎想不到一种在O（1）时间内获取中位数的方法。任何帮助都将不胜感激。

- Melissa Stewart

---

为什么不能在“插入”时像“总计”一样更新中位数（保存为（值，值之间的数量））？ - Abstraction

假设你的“store”有一个固定的（1000）元素数量，那么你编写的几乎任何计算中位数的代码都将是O(1)。 - Paul Hankin

@PaulHankin 它没有固定数量的元素。你可能需要再次阅读问题。 - Melissa Stewart

@抽象化 这就是我想做的，但似乎找不到方法。 - Melissa Stewart

@MelissaStewart 保罗是对的，store有固定数量的元素（1000个）。无论插入多少值都没有关系。请参见我的答案。 - Andreas

@MelissaStewart 你的初始化 store = new int[1000]; 保证了 store 具有固定数量的元素。你可能需要重新阅读你的代码。 - Lew Bloch

Answer 1

你已经完成了所有繁重的工作，通过构建store计数器。加上size值，就足够简单了。

你只需要开始迭代store，将计数相加，直到达到size的一半。如果size是奇数，那么这就是你的中位数值。对于偶数的size，你将获取两个相邻的值并取它们的平均值。

平均性能为O(1000/2)，这意味着O(1)，因为它不依赖于n，即使n达到数十亿，性能也不会改变。

请记住，O(1)并不意味着立即或甚至快速。正如Wikipedia所说：

如果T(n)的值受不依赖于输入大小的值限制，则称算法具有常数时间（也写作O(1)时间）。

在你的情况下，该限制为1000。

- Andreas

---

或许有些吹毛求疵，但 O(1) 并不意味着与 n 无关。例如，for (i = 0; i < n % 10000; i++) putchar('.'); 是 O(1) 的，因为它永远不会输出超过 10000 个项目，但运行时间取决于 n（具体来说，是 n 模 10000 的结果）。 - Paul Hankin

也许我没有理解你的意思，但是迭代一个列表并不能使算法的时间复杂度为O(1)。 - Melissa Stewart

在一个有限大小的列表上进行迭代是O(1)。做1000件事情是一项常量级的工作，因此也是O(1)。 - Paul Hankin

@PaulHankin 好的，那有帮助，我可以想到一个使用它的方法。 - Melissa Stewart

如果n达到数十亿级别，那么值将为1000000000/2。因此，它与n有关，而在这种情况下，n为1000。我们将获得线性时间，而不是常数时间。 - Alex Vovchuk

@AlexVovchuk 在这种情况下，“n”是1000吗？不，n是输入的数量，也就是插入的项数，即size的值，而不是store数组的长度，它始终为1000。这就是为什么getMedian()的时间复杂度为_O(1)_，因为进行该调用的性能与“n”无关，与insert()和getMean()方法的性能无关。 - Andreas

Answer 2

你可以读取的可能值非常有限 - 只有1000个。因此，你可以考虑实现类似于计数排序的东西 - 每次输入一个数字，就增加该值的计数器。

要在恒定时间内实现中位数，你需要两个数字 - 中位数索引（即中位数的值）和你已经读取并且在中位数左侧（或右侧）的值的数量。我在这里停一下，希望你能自己想出如何继续。

编辑（正如评论中指出的）：你已经有了排序后元素的数组（stored），并且你知道中位数左侧的元素数量（size/2）。你只需要将逻辑组合在一起即可。我想指出的是，如果你使用线性附加内存，你就不需要在每次插入时遍历整个数组。

- Ivaylo Strandjev

---

问题中的代码已经有你在第一段所说的计数器了。请查看store字段。 - Andreas

@Andreas，它缺少一个值——左侧（或右侧）中位数的值。使用这个值（和一点思考），我们不需要迭代所有可能的值。 - Ivaylo Strandjev

不要紧。这可以在 getMedian() 方法中完成。相对于 n，迭代 store 数组是常数时间。 - Andreas

是的，没错。而且这个常量大约是1000。使用我的建议，它可以被显著优化。 - Ivaylo Strandjev

@Andreas 实际上你是对的。不需要第二个值。 - Ivaylo Strandjev

Answer 3

对于一般情况，元素范围不受限制，基于任何比较算法都不存在这样的数据结构，因为它将允许O(n)排序。

证明：假设存在这样的数据结构，称之为D。
令A为排序的输入数组。（为简单起见，假设A.size()是偶数，可以通过添加垃圾元素并稍后丢弃它来轻松放宽这个条件）。

sort(A):
  ds = new D()
  for each x in A:
    ds.add(x)
  m1 = min(A) - 1
  m2 = max(A) + 1
  for (i=0; i < A.size(); i++):
    ds.add(m1)
  # at this point, ds.median() is smallest element in A
  for (i = 0; i < A.size(); i++):
    yield ds.median()
    # Each two insertions advances median by 1
    ds.add(m2)
    ds.add(m2)

声明1：该算法的时间复杂度为O(n)。 证明：由于我们有添加（add()）和中位数（median()）的常量操作，每次迭代它们的时间复杂度为O(1)，而迭代次数是线性的 - 因此该算法的时间复杂度为线性。

声明2：输出结果是按A数组排序的。 证明（指南）：在插入n个m1之后，中位数是A数组中最小的元素。每两次插入操作后，中位数向前移动一个位置，并且由于这种移动是有序的，因此总体输出结果是有序的。

由于上述算法的时间复杂度为O(n)，并且在比较模型下不可能实现，因此不存在这样的数据结构。

QED.

- amit

---

你的证明完全偏离了问题的范围，但仍然非常优雅。 - Melissa Stewart

@MelissaStewart 更新了解决方案，以捕获更广泛的计算模型（从排序而不是从元素唯一性进行缩减）。 - amit

@amit 的意思是，由于只有1000个可能的值，所以我们不处于一般情况。 - btilly

你为什么要谈论排序？你是在暗示在一般情况下无法在O(n)时间内找到中位数吗？快速选择算法可以在平均情况下以O(n)的时间复杂度选择中位数。 - MarredCheese