0

正と負の整数のセットが与えられた場合、すべての正の整数を片側に、負の整数を片側にグループ化します。番号は、表示される順序と同じにする必要があります。

例：

配列 = {1、-3、-5、9、-8}

O/P = {-3、-5、-8、1、9}

単純にループインして新しい配列を埋めることができるので、余分なスペースを使用することがこの問題に挑戦しているとは思いません。課題は、余分なスペースを使わずにその場で行うことです。この質問は私の友人から尋ねられました。

（私は2つのポインターでそれを解決し、正負を交換するなどを考えていましたが、すぐに要素が現れる相対的な順序がめちゃくちゃになったようです）

助言がありますか？

4

2 に答える 2

2

これは宿題のような気がするので、ヒントを出します。

安定ソートを適用します。

安定した並べ替えアルゴリズムは、等しいキーを持つレコードの相対的な順序を維持します。

同等性テストとして、数値の実際の値を使用しないでください。代わりに、正の数は他の正の数に等しいと考え、負の数は他の負の数に等しいと考えます。

于 2012-07-14T02:48:36.093 に答える
-1

これは O(n) にすることができます。以下はpythonでのサンプルコードです。クイックソートのようなピボットを使用すると、目的が解決されます。解決策は次のようになります-

def one_side_arrange(self, arr):
    i = -1
    for j in range(len(arr)):
        if (arr[j] < 0):
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    return arr

入力 Arr = [1,2,3,-1,2,-3,3,4,-3,-5] 出力 = [-1, -3, -3, -5, 2, 2, 3, 4 、3、1]

于 2019-12-26T11:09:36.927 に答える