在恒定时间内查找平均值和中位数

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)时间内获得中位数的方法.任何帮助赞赏.

Answer 1

你已经通过建造store柜台完成了所有繁重的工作.加上size价值,这很容易.

你只需要开始迭代store,总结计数直到达到一半size.那是你的中值,如果size是奇数.对于偶数size,您将获取两个周围的值并获得它们的平均值.

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

记住,O(1)并不意味着即时,甚至快.正如维基百科所说:

如果T(n)的值受不依赖于输入大小的值限制,则称算法是恒定时间(也写为O(1)时间).

在您的情况下,该范围是1000.

Answer 2

您可以读取的可能值非常有限 - 只有 1000。因此您可以考虑实现类似计数排序的功能- 每次输入数字时，您都会增加该值的计数器。

要在恒定时间内实现中位数，您将需要两个数字 - 中位数索引（即中位数的值）和您已读取的位于中位数左侧（或右侧）的值的数量。我就停在这里，希望你能够弄清楚如何自己继续。

编辑（如评论中指出的）：您已经拥有带有排序元素（）的数组stored，并且您知道中位数（）左侧的元素数量size/2。您只需要将逻辑粘合在一起即可。我想指出，如果您使用线性附加内存，则无需在每次插入时迭代整个数组。