algorithm - サブ配列を最小限に並べ替える

Question

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

Answer 1

観察

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

アルゴリズム

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

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

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

複雑

オン）

---

n についても同様です。

Answer 2

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

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

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

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

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

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