2

Web サイト (talentbuddy.co) でこの問題を見つけましたが、Big-O 表記法について私が知っているすべてが混同されています。

問題文は次のとおりです。

整数の配列が与えられた場合、タスクは標準出力 (stdout) に初期配列を出力することですが、特別な方法でソートされます。

すべての負の数が最初に来て、初期配列によるそれらの相対位置は正の整数と同じように変化しませんが、最後に来ます。

予想される複雑さ: O(N) 時間、余分なメモリ O(1)

入力例: -5 2 1 -2 3

出力例: -5 -2 2 1 3

O(n) 時間は、アルゴリズムの実行時間が入力のサイズ (この場合は配列のサイズ) に比例することを意味することを理解していますが、余分なメモリ O(1) を持つことはどういう意味ですか?

単一の for ループを使用してこの問題を解決することは可能ですか? これが私のソリューションの外観です。ランタイムが O(n) かどうかはわかりません。

    import java.util.Arrays;
class MyClass {
    public static void relative_sort(Integer[] v) {
        int[] positives = new int[v.length];
        int counter = 0;
        for(int i=0; i < v.length; i++){
            if(v[i] < 0){
                System.out.print(v[i] + " ");   
            }else{
                 positives[counter] = v[i];  
                 counter++;
            }
        }
        for(int i=0; i < counter; i++){
            System.out.print(positives[i] + " ");            
        }
    }
}

助けてくれてどうもありがとう！ほんとうにありがとう！

4

3 に答える 3

1

Extra Memory 制約は、使用する必要がある追加のメモリが一定の係数でなければならないことを意味します。つまり、入力のサイズに依存しない値であるxバイトのスペースが必要です。x

もちろん、データのサイズはそれ自体に比例するため、余分なメモリについて言及しているため、配列自体を超えて操作に使用する余分な（一時的な？）スペースを参照しています。

positivesソリューションでは、入力データに比例する配列を使用しています。これは明らかに O(n) 余分なメモリであるため、制約に適合しません。

于 2013-10-31T17:47:09.557 に答える
0

2 つのループを使用できますが、正の配列を取り除くだけです。代わりに、最初のループと同様のロジックを使用してください

class MyClass {
public static void relative_sort(Integer[] v) {
    for(int i=0; i < v.length; i++){
        if(v[i] < 0)
            System.out.print(v[i] + " ");   
    }
    for(int i=0; i < v.length; i++){
        if(v[i] >= 0)
            System.out.print(v[i] + " ");   
    }

}
}

複雑さはO(N)あり、余分な定数メモリは必要ありませんO(1)

于 2013-10-31T18:34:26.843 に答える