配列内の要素を再配置して、配列が別の配列に収まるかどうかを確認します

問題の説明から、2 つの配列が与えられた場合、最初の配列が 2 番目の配列に適合するかどうかを確認する必要があることがわかります。

現実の世界では、配列内の要素を並べ替えることによって、配列が別の配列に適合するかどうかを確認する必要がある状況が数多くあります。

さまざまな理由により、プログラマは配列の項目を再配置して、それらが別の配列に適合するかどうかを確認する必要がある場合があります。コンピュータープログラミングにおけるメモリ管理もその 1 つです。大量のデータを扱う場合、多くの場合、配列を使用してデータを保存する方が効率的ですが、メモリの制限により、メモリの制限を回避するために配列を特定の方法で配置する必要がある場合があります。

説明

は次のように翻訳されます:

説明

この問題を解読してみましょう。

2 つの配列があるとします。配列 A のサイズは n、配列 B のサイズは m です。ここで、m は n 以上です。このタスクは、配列 A が配列 B に完全に含まれるように配列 A の要素を再配置できるかどうかを確認することです。

言い換えると、配列 A のすべての要素は、配列 A と同じ順序で配列 B に存在する必要があります。ただし、配列 B には、配列 A に存在しない追加の要素が存在する可能性があります。

たとえば、配列 A には要素 [3,2,1] が含まれ、配列 B には要素 [2, 1, 3, 4, 5] が含まれるとします。以下に示すように、配列 A の要素を再配置して [3, 2, 1] を取得し、これを配列 B に完全に含めることができます。

一方、配列 A に要素 [1, 2, 3] が含まれ、配列 B に要素 [2, 3, 4, 5] が含まれる場合、配列 A の要素を配列 B に完全に収まるように再配置することはできません。配列 B には要素 1 がありません。

したがって、この場合、要素を並べ替えることによって配列 A が配列 B に収まるかどうかをチェックする関数は False を返します。

＃＃＃方法＃＃＃

プログラム全体をステップバイステップのアルゴリズムにデコードしてみましょう。

これら 2 つの配列を昇順に並べ替えます。

• 2 つの配列の要素を、各配列の最初のエントリから比較します。

• 小さい方の配列の要素が大きい方の配列の対応する要素以下である場合は、両方の配列の次の要素に移動し続けます。

• 小さい方の配列の要素が大きい方の配列の対応する要素よりも大きい場合、小さい方の配列は大きい方の配列に収まらないため、「false」を返します。

• 小さい配列のすべての項目が大きい配列の対応する要素以下である場合、小さい配列は大きい配列に収まるため、「true」を返します。
注

- 並べ替えステップにより、このアルゴリズムの複雑さは O(n log n) になります (n は配列のサイズです)。 ＃＃＃＃＃＃例＃＃＃

C コードの実装: 配列内の要素を再配置して、配列が別の配列に収まるかどうかを確認します リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃複雑＃＃＃

時間計算量

: O(n log n)。このコードでは、最初に 2 つの配列を並べ替えてから反復を実行するためです。

空間複雑度

: 2 つのベクトルの要素をメモリに保存するため、O(n)。

＃＃＃結論は＃＃＃

今回は、配列が別の配列に収まるかどうかをチェックする方法を説明してみました。この記事がこの概念をより深く理解するのに役立つことを願っています。

以上が配列内の要素を再配置して、配列が別の配列に収まるかどうかを確認しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。