2

[0..N-1] の範囲の値で埋められたサイズ [0..N-1] の配列をソートするアルゴリズムを作成する必要があります。配列内の値を繰り返すことはできません。並べ替えは線形時間で機能するはずであり、追加の変数のみを使用できるようにしました。

私が書いたコードにコメントしてください。私が推測する限り、最悪の時間は 2*N です。まだ線形時間ですか？より速くすることは可能ですか？

public int sort(){
    int i  = 0;             
    while (i < n){
        if (a[i] != i)      
            switchElements(a[i], a[a[i]]);                  
        else
            i++;                    
    }
    return count;
}

追加 1 本当に配列をソートする必要があります。ソートはタスクの一部にすぎないためです。完全なタスクは、線形時間で配列に重複する値があり、追加の変数がないことを見つけることです。

4

2 に答える 2

5

元の質問への回答：

繰り返されない要素[0..N-1]を含む要素を含む配列[0..N-1]

なぜソートするのですか？ソートされた配列はすでに既知であり、です[0..N-1]。

追加の1を考慮すると、アルゴリズムは正常に見えます。各要素を1回確認し、少なくとも1回は各要素を確認する必要があるため、改善することはできません。また2*NですO(N)。

于 2012-11-12T19:10:37.860 に答える
1

重複を検出するために、そのロジックをさらに拡張して、値をそれぞれのスポットに強制することができます。

public int sort(){
    int i  = 0;             
    while (i < n){
        while (a[i] != a[a[i]])      
            switchElements(a[i], a[a[i]]);                  
        ++i;                    
    }
    return count;
}

そして最後に、iと iがA[i]一致しない場合は、繰り返しを示します!
全体として、それはまだO(N)手順です。

詳細については、次の投稿を参照してください:
O(n) 時間と O(1) 空間での重複の検索

于 2012-11-12T19:39:44.590 に答える