arrays - 並べ替えられていない配列を指定して、線形時間および定数空間で i < j および A[i] < A[j] となる i、j を見つけます

Question

例 1:

入力: 5 4 3 2 1

出力: なし

例 2:

入力: 5 4 3 2 6 1

出力: 0、4 (インデックス)

i < j および A[i] < A[j] であるようなインデックス i、j を線形時間および一定の余分な空間で見つけるアルゴリズムを提案してください。O(n^2)2つのforループを使用して解決しました。

Answer 1

ええと... 私はすぐに仮定iを立てjます。もしそうなら、アルゴリズムは配列上で簡単な単一パスに変わります。ijj == i + 1A[i] < A[j]

2 番目の例では、i = 3andになりj = 4ます。

i確かに、私たちが見つけたとしましょうそしてjそのような それA[i] < A[j]そしてi + 1 < j. を見てみましょうA[i + 1]。A[i + 1]が より大きい場合はA[i]、設定j = i + 1するだけで完了です。それ以外の場合、A[i + 1]が より小さいか等しい場合はA[i]、設定i = i + 1して繰り返します。これにより、常に要件j == i + 1を満たすペアが導き出されA[i] < A[j]ます。

言い換えれば、A[i] < A[i + 1]状況を探して配列を調べるだけです。それだけです。