采访街中位挑战

Question

问题M数的中值定义为1)如果M是奇数中间数，然后按2顺序排序)，如果M是中间2数的平均数(排序后同样如此)，那么首先有一个空的数字列表。然后可以从列表中添加或删除某些数字。对于每个添加或删除操作，输出列表中数字的中位数。

例:对于一组m=5的数，{ 9，2，8，4，1 }，中位数是排序集{ 1，2，4，8，9}中的第三个数，它是4。同样，对于m= 4，{ 5，2，10，4}的集合，中值是排序集{ 2，4，5，10 }中第二和第三个元素的平均值，即(4+5)/2 = 4.5。

我的方法我认为这个问题可以用这种方式解决。其思想是使用以前的中值值和指针来查找新的中值值，而不是在每次添加或删除操作时重新计算。

1)使用多个集合，这些集合总是保持元素的顺序，并允许重复。换句话说，以某种方式维护排序列表。

2)如果添加操作

2.1) Insert this element into set and then calculate the median

2.2) if the size of set is 1 then first element will be the median

2.3) if the size of set is even, then

           if new element is larger then prev median, new median will be avg of prev median

               and the next element in set.

           else new median will be avg of prev median and previous of prev element in the set.

2.4) if the size is odd, then

          if new element is larger then prev median

                 if also less then 2nd element of prev median ( 2nd element used to calculate avg

                    of prev median) then this new element to be added will be new median

                 else median will be 2nd element use to calculate the avg during last iteration prev

                    median.

          else

                 new median will be previous of prev median element in the set

3)如果手术被移除

3.1) First calculate the new median

3.2) If the size of set is 0 can't remove

3.3) If the size is 1 if the first element is the element to be removed, remove it else can't remove.

3.4) If the size of set is even, then

           if the element to be deleted is greater than or equal to 2nd element of prev median, then

               1st element of prev median will be new median

          else 2nd element of prev median will be the new median

3.5) If the size of set is odd, then

           if the element to be deleted is the prev median then find the avg of its prev and  next element.

           else if the element to be deleted is greater then prev median, new median will be avg of prev median and previous to prev median

           else median will be avg of prev median and next element to prev median.

3.6) Remove the element. 

这是工作代码.http://justprogrammng.blogspot.com/2012/06/interviewstreet-median-challenge.html。你对这种方法有什么看法？

Answer 1

您的方法似乎是可行的，但从描述和代码中可以看出，涉及的个案工作很多。我不想成为那个要调试的人！因此，让我给你们一个替代的解决方案，应该涉及较少的情况，因此更容易得到正确的。

保持两个多集(此算法也适用于两个优先级队列，因为我们将只查看每个队列的极值)。第一个，minset，将保持最小的n/2数，第二个，maxset，将存储最后一个n/2数。

无论何时添加一个数字：

如果它大于maxset

• Otherwise，，则将其添加到minset

中

请注意，这并不保证n/2条件。因此，我们应该增加一个额外的“修复”步骤：

如果是minset.

• If maxset.

，则从maxset中删除最小的元素并将其插入到maxset.size() > minset.size() minset.size() > minset.size() + 1，从minset中删除最大的元素并将其插入到

做完这件事后，我们只需要得到中位数。这在我们的数据结构中应该很容易做到:取决于当前n是偶数还是奇数，它要么是max(minset)，要么是max(minset)和min(maxset)之间的平均值。

对于删除操作，只需尝试将其从任何集合中移除，然后进行修复。

Answer 2

代码的主要问题是将每个新项与运行中的中位数进行比较，这可能是计算出的平均值。相反，您应该将新项与前面中间的值(代码中的*prev)进行比较。在接收到1和5的顺序后，您的中值将为3。如果下一个值为2或4，则它将成为新的中值，但是由于您的代码对每个中间值遵循不同的路径，其中一个结果是错误的。

从整体上来说，只跟踪中间位置而不是运行中位就更简单了。相反，计算每个add/remove操作结束时的中位数：

if size == 0
    median = NaN
else if size is odd
    median = *prev
else
    median = (*prev + *(prev-1)) / 2

Answer 3

我认为你可以试着核实两起案件：

1) negative number
4
a -1
a 0
a 0
r 0

2) two big integer whose sum will exceed max int