1

私はinterviewstreetの中央値の課題を解決しようとしています。私はここに同様の質問が投稿されているのを見ました：interviewstreet中央値チャレンジですが、私のアプローチの何が問題になっているのかを知りたいです。バイナリ検索とソートされたArrayListを使用して、各ポイントの中央値を見つけています。1番目、3番目、10番目のテストのみが合格し、残りはすべて間違った回答で失敗します。質問： http： //pastebin.com/1QhbiB2U コードは次のとおりです。

/**
 * @param args
 */
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    long N = in.nextLong();
    List<Long> list = new ArrayList<Long>();
    for(int i=0; i<N; i++){
        String op = in.next();
        long number = in.nextLong();
        performOperation(op, number, list);
    }
}

private static void performOperation(String op, long number, List<Long> list) {
    int index = Collections.binarySearch(list, number);
    if(op.equalsIgnoreCase("r")){
        if(index < 0){
            System.out.println("Wrong!");//Doesn't exist
            return;
        }else{
            list.remove(index);//Remove any one occurence
        }
    }else{
        if(index < 0){
            list.add(-index-1, number);//Add in sorted list
        }else{
            list.add(index, number);//Add where the same number exists, should still be sorted.
        }
    }

    if(list.size() == 0){
        System.out.println("Wrong!");
    }else if(list.size()%2 == 0){
        double median = (list.get(list.size()/2) + list.get(list.size()/2 - 1))/2.0;
        if(median == Math.ceil(median))
            System.out.println((long)median);
        else
            System.out.println(median);
    }else{
        System.out.println(list.get((list.size()-1)/2));
    }
}
4

1 に答える 1

3

添付プログラムの double の出力に問題があると思います。入力用の質問からそのプログラムを確認しました：

2
a 1
a 1000000000

与えます：

1
5.000000005E8

このような変更は上記のケースで機能します (あまり良くありませんが):

long median = (list.get(list.size()/2) + list.get(list.size()/2 - 1));  // median is multiplied by 2
    if(1==(median&1))
        //odd
    System.out.println(""+(median/2)+".5");
else
    System.out.println(median/2);

また、インデックス付きの ArrayList.add は O(n) であることに注意してください。

于 2012-06-20T21:05:45.527 に答える