これはインタビューの質問です。整数の配列を指定して、要素 m から n までを並べ替えた場合に配列全体が並べ替えられるように、インデックス m と n を見つけるメソッドを作成します。nm を最小化します。つまり、最小のシーケンスを見つけます。
1014 次
2 に答える
6
観察
m の前の整数は昇順で、後の整数よりも小さい (または等しい) 必要があります。
アルゴリズム
最初の要素から開始し、最初の減少で停止します。(サブアレイ SA)
後の最小値を見つけます。(分)
開始点は、MIN より小さい (または等しい) SA の最大整数の直後です。(m が見つかりました)
複雑
オン)
n についても同様です。
于 2012-11-28T16:52:21.447 に答える
4
次の 4 つのことを追跡する必要があります。
- 先頭のソートされた領域の終わり
- 最後に並べ替えられた領域の開始
- 開始領域の後の最小番号
- 終了領域の前の最大数
1 と 2 の仮の値を把握することから始めます。配列を最初から最後までスキャンして、間違った値が見つかるまで調べます。
次に、予備の 1 の後にすべてをスキャンして、最小数を見つけます。これがあなたの 3 です。同様に 4 を見つけます。
ここで、最小値があるべき場所が見つかるまで、配列の開始領域をバックトラックします。これは 1 に対する正確な答えであり、あなたのm
.
n
同様に、最後の領域をバックトラックして、最大数がどこにあるべきかを見つけます。
于 2012-11-28T16:54:03.093 に答える