7

问题 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。您对这种方法有何看法？

4

6 回答 6

4

您的方法似乎可行，但是从描述和代码中，您可以看出涉及很多案例工作。我不想成为那个必须调试的人！因此，让我为您提供一个替代解决方案，该解决方案应该涉及更少的案例，因此更容易正确处理。

保留两个多重集（这个算法也适用于两个优先级队列，因为我们只看每个的极端）。第一个，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)

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

于 2012-06-13T18:51:09.670 回答
1

我认为您可以尝试验证两种情况：

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

2) two big integer whose sum will exceed max int
于 2012-06-14T23:50:13.250 回答
1

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

总体而言，只跟踪中间位置而不是运行中位数会更简单。相反，在每个添加/删除操作结束时计算中位数：

if size == 0
    median = NaN
else if size is odd
    median = *prev
else
    median = (*prev + *(prev-1)) / 2
于 2012-06-13T23:05:46.423 回答
0

这是使用 collections.sort(list) 在 java 中的中位数挑战的解决方案

import java.util.*;
public class SolutionMedian{
    ArrayList<Integer> sortedList = new ArrayList<Integer>();

    public static void main(String args[]){

        SolutionMedian m = new SolutionMedian();

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        char[] op = new char[n];
        int[] val = new int[n];
        for(int i=0; i<n; i++){
            op[i] = in.next().charAt(0);
            val[i] = in.nextInt();
        }

        for(int i=0; i<n; i++)
            if(op[i] == 'a') 
                m.add(val[i]);
            else 
                m.remove(val[i]);
    }

void add(int val){
        sortedList.add(val);
        getMedian();
    }

    void remove(int val){
        int index = sortedList.indexOf(val);
        if(index>=0){
            sortedList.remove(index);
            getMedian();
        }else{ 
            System.out.println("Wrong!");
        }
    }

    void getMedian(){
        Collections.sort(sortedList);
        int size = sortedList.size();
        switch(size){
            case 0: 
                System.out.println("Wrong!");
                break;
            case 1: 
                System.out.println(sortedList.get(0));
                break;
            default: 
                if(size%2 == 0) {//even size
                    int halfIndex = size/2;
                    long sum = sortedList.get(halfIndex)
                              + sortedList.get(halfIndex-1);
                    if(1==(sum&1)) 
                        System.out.println((sum/2)+".5");
                    else 
                        System.out.println(sum/2);
                }else{//odd size
                    System.out.println(sortedList.get((size-1)/2));
                }
        }
    }
}
于 2013-03-21T11:32:41.993 回答
0

此代码解决了 interviewStreet 上的中位数挑战。

# this code solves the median challenge on interviewStreet.
# logic is simple. insert the numbers into a sorted sequence in place.
# use bisection to find the insert index(O(logn)). keep a count of no. of elements in
# the list and print the median using it(O(1)).
!/bin/python
from bisect import bisect_left
List = [] 
nnode = 0 

def printMed():
if nnode>0:
    if nnode%2 == 0 :
    if (0.5*(List[nnode/2]+List[(nnode/2)-1])).is_integer():
        print int(0.5*(List[nnode/2]+List[(nnode/2)-1]))
    else:
        print 0.5*(List[nnode/2]+List[(nnode/2)-1])
    else:
    print List[nnode/2]
else:
    print "Wrong!"

def rem(val):
global nnode
try:
        List.remove(val)
except:
    print "Wrong!"
else:
    nnode = nnode-1
    printMed()

if __name__ == "__main__":
    n = int(raw_input())
for i in range(0,n):
    l = raw_input().split()
    if(l[0] == 'r'):
        rem(int(l[1]))
    else:
    index = bisect_left(List , int(l[1])) ;
    List.insert(index ,int(l[1]))
    nnode = nnode+1 
    printMed()
于 2013-01-08T07:44:47.497 回答
0

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

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)
于 2012-06-13T04:30:02.680 回答