Javaで非降順配列を実装する方法

#問題の説明

n 個の整数を含む配列が与えられた場合、あなたのタスクはチェックすることです。最大 1 つの要素を変更するだけで非子孫にできるかどうか。非降順配列は、すべての i (1

サンプル 1:

ⅰ 入力: [4,2,3]

ii 出力: True

ⅲ 説明:最初の数値 4 を 1 に変更すると、[1,2,3] を非降順配列として取得できます。

サンプル 2:

ⅰ 入力: [ 4,2,1]

ii 出力: False

ⅲ 説明: 最大 1 つの要素を変更することによって配列を非降順にすることはできません。

問題解決アイデアの分析

a. 単純に考えると、次の 3 つの状況が発生する可能性があります。要素の変更は条件を満たし、要素の変更は条件を満たしますが、要素の変更は条件を満たしません。最初のケースでは、配列を走査して、配列内の各項目が前の項目以上であるかどうかを確認し、そうであれば true を返します。 2 番目のケースでは、変更する数値 array[i] を列挙し、array[i] の前の数値が減少していないかどうか、および array[i] の後の数値が減少していないかどうかを確認できます。 最後に、array[i-1] が true かどうかも確認する必要があります (array[i] が次の値であるかどうかを確認する必要はありません)境界), true の場合、array[i] を array[i-1] と array[i 1] の間の任意の数に変更して、配列を非降順配列にすることができます。これはケース 2 で、true を返します。すべての i に対して true ではない場合、ケース 3 については false を返します。これを行う場合の時間計算量は O(n^2) で、追加の空間計算量は O(1) です。

b. 数値を変更した後、減少しない配列に変更するにはどのような条件を満たすことができますか?明らかに、そのような配列は、非減少条件を満たさない隣接する数値のペアが 1 つだけ存在するという条件を満たす必要があります。つまり、array[i を満たす一意の i (1array[i]、そのような i が複数ある場合、元の配列は最大 1 つの数値を変更するだけでは非降順配列になることはできないと言えます。では、この条件を満たす配列は、数値を変更することで非減少を満たすことができるのでしょうか?いいえ、たとえば[2,4,1,3]のように、隣接する4,1だけが非減少を満たしていませんが、1つの数字を変更しただけでは非減少にはなりません。実際、array[i-1]>array[i] を満たす i が 1 つだけある場合、変更する数値は 2 つの数値 array[i-1] と array[i] の間になければなりません。前のアプローチを適用して、2 つの状況に対して別々の判断を下すことができます。さらに、array[i-1]>array[i] は i についてのみ真であるため、他の隣接する数値はすべて非減少条件を満たすため、array[i-1] についてはその前後の配列が成り立つと言われますはそれぞれ非降順条件を満たしており、array[i]も同様であるため、前後の2つの配列を非降順配列として接続できるかどうかを判断するだけで済みます。具体的には、変更する番号が array[i-1] の場合、array[i-2]array[i]、最終的に true を返す条件は array[i-1]、array[i] が境界、または配列[i-2]

参考プログラム

Java バージョン:

以上がJavaで非降順配列を実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。