8

これはインタビューの質問です。整数の配列を指定して、要素 m から n までを並べ替えた場合に配列全体が並べ替えられるように、インデックス m と n を見つけるメソッドを作成します。nm を最小化します。つまり、最小のシーケンスを見つけます。

4

2 に答える 2

6

観察

m の前の整数は昇順で、後の整数よりも小さい (または等しい) 必要があります。

アルゴリズム

  1. 最初の要素から開始し、最初の減少で停止します。(サブアレイ SA)

  2. 後の最小値を見つけます。(分)

  3. 開始点は、MIN より小さい (または等しい) SA の最大整数の直後です。(m が見つかりました)

複雑

オン)


n についても同様です。

于 2012-11-28T16:52:21.447 に答える
4

次の 4 つのことを追跡する必要があります。

  1. 先頭のソートされた領域の終わり
  2. 最後に並べ替えられた領域の開始
  3. 開始領域の後の最小番号
  4. 終了領域の前の最大数

1 と 2 の仮の値を把握することから始めます。配列を最初から最後までスキャンして、間違った値が見つかるまで調べます。

次に、予備の 1 の後にすべてをスキャンして、最小数を見つけます。これがあなたの 3 です。同様に 4 を見つけます。

ここで、最小値があるべき場所が見つかるまで、配列の開始領域をバックトラックします。これは 1 に対する正確な答えであり、あなたのm.

n同様に、最後の領域をバックトラックして、最大数がどこにあるべきかを見つけます。

于 2012-11-28T16:54:03.093 に答える