3

重複の可能性:
O(N) 回の移動のみで安定したインプレース バイナリ パーティションを実行できるアルゴリズムはどれですか?

これは私が打たれたインタビューの質問の 1 つです。

質問: 正と負の両方の整数の配列が与えられ、正の数を一方の側にシフトし、負の数を反対側にシフトする必要があります。元。{-1,5,3,-8,4,-6,9} から {-1,-8,-6,5,3,4,9}。これは O(n) で、追加の array なしで行う必要があります。

最初に、次のようなクイックソートを介してこれを行うことで考えました

疑似コード

ゼロに最も近い要素を見つけます。それをピボット要素にします。次に、配列にクイックソートの 1 つのパスを適用します。これは O(n) です。

ああ！しかし、クイックソートは安定したソートではありませんか?

その後、次の解決策がありました

擬似コード:

最初に、最初の +ve 番号まで current を増加させ、最後の -ve 番号まで減少させます。

current が負の場合、 current をインクリメントします current が正の場合、 end の要素と交換し、 current をデクリメントして両方とも end current >= end の場合、ブレークします。

まだ正しい答えを得ていません。これに関する提案が必要

4

2 に答える 2

0

std::stable_partition はまさにあなたが望むことを行います。

C++11 の場合は、

std::stable_partition(
  array.begin(), array.end(),
  [] (int i) { return i < 0; });
于 2012-07-05T04:24:27.903 に答える
0

結果配列がソース配列と異なる場合は、2 つのパスで簡単に行うことができます。

p = 0;   //current index in result array

For i = 0 to length - 1 :
    If source[i] < 0 then
        result[p] = source[i]
        increment p
    End if
End for

For i = 0 to length - 1 :
    If source[i] >= 0 then
        result[p] = source[i]
        increment p
    End if
End for

その場でやりたい場合は、少しトリッキーです。バブル タイプの並べ替えを試すこともできますが、これは O(n^2) です。

n = 0  // number of negative items found

For i = 0 to length - 1 :
    If array[i] < 0 then
        For j = i - 1 downto n :
            swap array[j+1] and array[j]
        End for

        increment n
    End if
End for

残念ながら、O(n) であり、追加の配列の割り当てを必要としないソリューションは考えられません。

于 2012-07-05T06:00:37.460 に答える