interviewstreet位数挑战 [英] interviewstreet median challenge

问题描述

问题 m个的中间值被定义为 1）如果M是奇数中间的数字，以便对它们进行排序后， 2）如果排序后M是偶数的中间两个数的平均数（再次） 你必须在第一空号列表。然后，您可以添加或删除列表中的一些数字。对于每一个添加或删除操作时，输出数字的列表中的中位数。

Problem The median of M numbers is defined as the 1) if M is odd middle number after sorting them in order 2) if M is even the average number of the middle 2 numbers (again after sorting) You have an empty number list at first. Then you can add or remove some number from the list. For each add or remove operation, output the median of numbers in the list.

例：对于一个集合M = 5的数字，{9,2，8,4，1}中位数是有序集合第三个数字{1，2，4，8，9}这是4类似对于组m为4，{5,2，10，4}，中位数是第二{，10 2，4，5}（4 + 5）/ 2的平均值，并在有序集合的第三元件，其是= 4.5

Example : For a set of m = 5 numbers, { 9, 2, 8, 4, 1 } the median is the third number in sorted set { 1, 2, 4, 8, 9 } which is 4. Similarly for set of m = 4, { 5, 2, 10, 4 }, the median is the average of second and the third element in the sorted set { 2, 4, 5, 10 } which is (4+5)/2 = 4.5

我的做法 我认为这个问题可以通过这种方式来解决.. 想法是使用previous中值与指针找到代替重新计算在每次添加或删除操作的新的中值

My approach I think the problem can be solved in this way.. Idea is to use previous median value and pointer to find new median value instead of recalculating at every add or remove operation.

1）使用多集其始终保持要素，以便和允许重复。换句话说保持排序列表莫名其妙。

1) Use multisets which always keep elements in order and allow duplicates. In other words maintain sorted list somehow.

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) If the operation is 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. 

下面是工作code ...... HTTP：/ /justprogrammng.blogspot.com/2012/06/interviewstreet-median-challenge.html 。什么是这种方法的意见？

Here is the working code ...http://justprogrammng.blogspot.com/2012/06/interviewstreet-median-challenge.html. What are your views on this approach?

推荐答案

您的做法似乎是它可以工作，但是从描述和code，你可以告诉大家，有很多个案涉及。我不希望成为一个不得不调试！因此，让我给你说应该涉及较少的情况下，因此要简单得多得到正确的替代解决方案。

Your approach seems like it could work, but from the description and the code, you can tell that there is a lot of casework involved. I wouldn't like to be the one having to debug that! So let me give you an alternate solution that should involve less cases, and therefore be much simpler to get right.

请2多集（该算法也适用于两个优先队列，因为我们只是要看看每个人的极限）。第一， MINSET ，是要保持最小的n / 2号，第二个， maxset ，是怎么回事存储最近n / 2号。

Keep two multisets (this algorithm also works with two priority queues, as we're only going to look at the extremes of each one). The first, minset, is going to keep the smallest n/2 numbers, and the second, maxset, is going to store the last n/2 numbers.

只要添加一个数字：

• 如果它大于 MAX（MINSET），将其添加到 maxset
• 否则，将其添加到 MINSET

• If it is greater than max(minset), add it to maxset
• Otherwise, add it to minset

请注意，这并不能保证N / 2的条件。因此，我们应该加上一个额外的固定的步骤：

Note that this doesn't guarantee the n/2 condition. Therefore, we should add one extra "fixing" step:

• 如果 maxset.size（）＆GT; minset.size（），从 maxset 删除最小的元素，并将其插入到 MINSET
• 如果 minset.size（）＆GT; minset.size（）+ 1 ，从 MINSET 删除最大的元素，并将其插入到 maxset 。

• If maxset.size() > minset.size(), remove the smallest element from maxset and insert it to minset.
• If minset.size() > minset.size() + 1, remove the biggest element from minset and insert it to maxset.

在这样做了，我们只需要获得中位数。这应该是很容易与我们的数据结构：根据当前n是否偶数或奇数，它要么 MAX（MINSET）或之间的平均 MAX（MINSET）和分（maxset）。

After this is done, we just have to get the median. This should be really easy to do with our data structure: depending on whether the current n is even or odd, it's either max(minset) or the average between max(minset) and min(maxset).

有关删除操作，只是试图从任何套之后将其删除，并做固定。

For the removal operation, just try to remove it from any of the sets and do the fixing afterwards.

这篇关于interviewstreet位数挑战的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！