Interviewstreet中位数挑战

Question

Interviewstreet中位数挑战

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）使用 multiset（多重集合），它们始终按顺序保留元素并允许重复。换句话说，以某种方式维护排序的列表。

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。您对此方法有何看法？

- sachin

当我删除中位数时，你的代码会出现奇怪的问题，例如："4 a 1 a 1 a 1 r 1"。 - ffao

谢谢 ffao，那是个小错误，现在已经纠正了。但仍然有一些问题我无法找到... - sachin

%g在行为上表现不佳，尝试使用更大的中位数和x值进行测试，它将以科学计数法打印。 - amitkarmakar

@vsaxena 对的，那就是我正在尝试做的事情，但不确定我的方法是否正确。 - sachin

好的，抱歉 - 我看到可以通过使用两个集合来进行优化，我会更改代码。 - gizmo

显示剩余6条评论

6个回答

1

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

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

2) two big integer whose sum will exceed max int

- nybon

不错的测试用例，帮助我捕捉了一个bug！ - gkuzmin

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

- xan

@观众们，可以在这里查看代码：http://justprogrammng.blogspot.in/2012/06/interviewstreet-median-challenge.html - sachin

@sachin Xan建议的核心和我一样，就是移除case语句。用更少的case语句通常意味着代码流程更加流畅，而且调试也更容易。 - ffao

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()

- girish sathyanarayana

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)

- Matt Dodge

最优解是在插入和删除时都为O(log n)，同时保持中位数操作为O(1)。 - ffao

我在C++中使用了multiset，其中插入和删除的时间复杂度为O(logn)，而使用我提到的方法找到中位数的时间复杂度为O(1)。 - sachin

你的逻辑是错误的。如果长度 % 2 == 0，则列表长度为偶数。将其更改为！=，它就是正确的。此外，您正在使用 length/2，它被截断下来，这是正确的。但是，然后您有 length/2 - 1，它被截断并降低了1。它应该是 length/2 + 1。如果 length/2 是 7.5，您想要 7 和 8，而不是 7 和 6。 - JustinDanielson

@JustinDanielson 假设列表是基于0的，那么逻辑是正确的。如果一个数组的长度为8（偶数），那么你想要第4个和第5个元素，在基于0的数组中它们的偏移量分别为3和4。同样的逻辑也适用于奇数长度。 - Matt Dodge

这就是我所说的保持指针的意思，就像 OP 所做的那样。如果你想要保持 O(log n) 的插入声明，你需要更改你的中位数伪代码，不使用数组索引。 - xan

显示剩余5条评论

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));
                }
        }
    }
}

- cocoper

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ffao · Accepted Answer

你的方法似乎可行，但从描述和代码中可以看出，涉及到很多特例处理。我不想成为调试的那个人！因此，让我给你提供一个替代方案，它应该涉及的特例较少，因此更容易正确实现。

保留两个multisets（这个算法也适用于两个优先队列，因为我们只会查看每个队列的极端值）。第一个minset将保留最小的n/2个数字，而第二个maxset将存储最后的n/2个数字。

每当添加一个数字时：

- 如果它大于max(minset)，则将其添加到maxset中。 - 否则，将其添加到minset中。

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

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

完成此操作后，我们只需获取中位数。使用我们的数据结构应该很容易实现：根据当前n是偶数还是奇数，它可能是max(minset)或max(minset)和min(maxset)的平均值。

对于删除操作，请尝试从任何一个集合中删除它，然后进行修复。