7

問題 M 数の中央値は次のように定義されます 1) M を順番に並べ替えた後の真ん中の数字が奇数の場合 2) M が真ん中の 2 つの数字の平均数である場合 (再び並べ替え後) 最初は空の数字リストがあります. 次に、リストに番号を追加または削除できます。追加または削除操作ごとに、リスト内の数値の中央値を出力します。

例 : m = 5 個の数値のセット { 9, 2, 8, 4, 1 } の場合、中央値は並べ替えられたセット { 1, 2, 4, 8, 9 } の 3 番目の数値である 4 です。 m = 4, { 5, 2, 10, 4 }、中央値は、並べ替えられたセット { 2, 4, 5, 10 } の 2 番目と 3 番目の要素の平均であり、(4+5)/2 = 4.5 です。

私のアプローチ は、この方法で問題を解決できると思います.アイデアは、追加または削除操作ごとに再計算するのではなく、以前の中央値とポインターを使用して新しい中央値を見つけることです。

1) 常に要素を順番に保持し、重複を許可するマルチセットを使用します。言い換えれば、ソートされたリストを何らかの形で維持します。

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 . このアプローチについてどう思いますか?

4

6 に答える 6

4

あなたのアプローチはうまくいくように見えますが、説明とコードから、多くのケースワークが関係していることがわかります。私はそれをデバッグしなければならない人になりたくありません! そこで、より少ないケースを含む必要があるため、より簡単に正しく行うことができる代替ソリューションを紹介しましょう。

2 つのマルチセットを保持します (このアルゴリズムは 2 つのプライオリティ キューでも機能します。それぞれの極値のみを調べるためです)。最初の ,minsetは最小の n/2 数値を保持し、2 番目の ,maxsetは最後の n/2 数値を格納します。

数字を追加するときはいつでも：

  • より大きい場合はmax(minset)、 に追加します。maxset
  • それ以外の場合は、追加しますminset

これは n/2 条件を保証しないことに注意してください。したがって、「修正」手順を 1 つ追加する必要があります。

  • の場合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

コードの主な問題は、新しい各アイテムと実行中の中央値との比較です。これは、計算された平均値である可能性があります。代わりに、新しいアイテムを前の中央の値（*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 に答える
1

次の 2 つのケースを確認してみてください。

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 に答える
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 に答える
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 に答える