algorithm - 采访街道中值挑战

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) 使用 multisets，它始终保持元素有序并允许重复。换句话说，以某种方式维护排序列表。

2) 如果操作是add

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) 如果操作是remove

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 个数字。

每当您添加一个数字时:

• 如果大于max(minset)，将其加入maxset
• 否则，将其添加到minset

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

• 如果 maxset.size() > minset.size()，从 maxset 中移除最小元素并将其插入到 minset。
• 如果 minset.size() > minset.size() + 1，从 minset 中移除最大的元素并将其插入到 maxset .

完成后，我们只需要获得中位数即可。这对我们的数据结构来说应该很容易做到:根据当前 n 是偶数还是奇数，它要么是 max(minset) 要么是 max(minset) 之间的平均值> 和 min(maxset)。

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