指定された操作によって配列を最大 1 つの要素に削減します

この問題では、ラウンドごとに指定された演算を実行することで、配列のサイズを 1 または 0 に減らします。

各ラウンドで配列をソートして、各反復で最大の要素を取得できます。さらに、head データ構造を使用してコードのパフォーマンスを向上させることもできます。

問題文 - nums[] 配列が与えられています。次のようにして配列を減らす必要があります。

• 配列内の最大の 2 つの要素を選択します。

• 2 つの要素が同じ場合は、配列から 2 つの要素を削除します。

• 2 つの要素が同じでない場合は、配列から 2 つの要素を削除し、abs(first − Secondary) を配列に挿入します。

配列の最後の要素を出力します。配列が空の場合は、0 を出力します。

＃＃＃＃＃＃例＃＃＃＃＃＃ ＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー

イラスト

最初のラウンドでは、9 と 8 を取得し、その差を配列に追加します。したがって、配列は [5, 3, 2, 5, 1] となります。

2 ラウンド目は 5 と 5 を取ります。したがって、配列は[3, 2, 1]になります。

次のラウンドは 3 と 2 を取ります。したがって、配列は [1, 1]

になります。

• 最終ラウンドでは1と1を取ります。したがって、配列は空になり、0 が出力されます。

• ＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー
  説明
- 5 のペアを 2 回削除すると、配列には 5 が 1 つ残ります。
• ＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー
  説明 -
まず、8と7を選択します。したがって、配列は [4, 1, 6] になります。その後、4と6を選択します。したがって、配列は[1, 2]になります。最後の操作では、配列は [1] になります。

• 方法1

このメソッドでは、配列のサイズが 1 または 0 になるまで配列を反復処理します。各反復では、配列をソートし、ソートされた配列の最初の 2 要素に対して指定された操作を実行します。最後に、配列サイズに基づいて出力を出力します。

＃＃＃アルゴリズム＃＃＃

ステップ 1- 配列のサイズを「len」変数に保存します。

ステップ 2- while ループを使用して配列の走査を開始します。

ステップ 3- ループ内で sort() メソッドを使用して、配列を逆に並べ替えます。

ステップ 4- 配列の最初と 2 番目の要素を取得します。また、配列の最初の要素と 2 番目の要素の差を計算します。

ステップ 5- 差が 0 の場合は、配列の最初の 2 つの要素を削除し、「len」を 2 減らします。差が 0 でない場合は、最初の 2 つの要素を削除し、'len' から 1 を減分します。

ステップ 6- 最後に、配列のサイズが 0 の場合は 0 を返します。それ以外の場合は、配列の最初の要素が返されます。

＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量 - O(N*NlogN)。O(N) は配列の反復に使用され、O(NlogN) は各反復で配列の並べ替えに使用されます。

空間複雑度 - 配列をソートするには O(N)。

方法 2

このアプローチでは、ヒープ データ構造を実装する優先キューを使用します。要素は常にソートされた順序で格納されます。したがって、最初の 2 つの最大の要素を簡単に削除できます。 ＃＃＃アルゴリズム＃＃＃

ステップ 1

- 「p_queue」という名前の優先キューを定義します。

ステップ 2

- すべての配列要素を優先キューに挿入します。

ステップ 3

- 優先キューのサイズが 1 より大きくなるまで繰り返します。

ステップ 4

- 優先キューの最初の 2 つの要素を 1 つずつ削除します。

ステップ 5

- 2 つの要素の違いを見つけます。

ステップ 6

- 差が 0 でない場合は、優先キューにプッシュします。

ステップ 7

- 最後に、キュー サイズが 0 の場合は 0 を返します。

ステップ 8

- それ以外の場合は、キューの先頭にある要素を返します。

＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量 - 優先キュー内の要素の挿入と削除の時間計算量は O(NlogN) です。

スペースの複雑さ - 優先キューに要素を格納するには O(N)。

優先キューのデータ構造は、要素の挿入または削除後に配列データを特定の順序で配置する必要がある場合に常に役立ちます。ヒープ データ構造を実装することで、挿入と削除が可能になります。

以上が指定された操作によって配列を最大 1 つの要素に削減しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。