面试中心挑战

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

如果您的列表已排序，那么您可以使用类似于以下伪代码的方法在恒定时间内计算中位数

if list.length % 2 == 0 
   median = (list[list.length/2 - 1] + list[list.length/2]) / 2 
else
   median = list[list.length/2]

因此，只需在每次插入/删除时维护一个排序列表即可。您可以O(n)通过逐步浏览列表直到位于 < 添加的元素和 >= 添加的元素之间的元素来及时执行这些操作。O(log n)如果您从列表的中间开始，然后决定您的元素是小于还是大于中间元素，您实际上可以及时执行这些插入/删除操作。取出那半个列表，从中间开始，然后重复。

您的问题没有说明对此的性能要求是什么，但据我所知，整个事情并不总是在恒定时间内发生。该实现具有以下性能

Insert    O(log n)
Remove    O(log n)
Median    O(1)