目次
時間計算量 - O(N*NlogN)。O(N) は配列の反復に使用され、O(NlogN) は各反復で配列の並べ替えに使用されます。
方法 2
- 差が 0 でない場合は、優先キューにプッシュします。
- それ以外の場合は、キューの先頭にある要素を返します。
スペースの複雑さ - 優先キューに要素を格納するには O(N)。
ホームページ バックエンド開発 C++ 指定された操作によって配列を最大 1 つの要素に削減します

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

Aug 29, 2023 pm 02:25 PM
配列演算により要素が削減される

指定された操作によって配列を最大 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 サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

C言語関数によって返される値の種類は何ですか?返品値を決定するものは何ですか? C言語関数によって返される値の種類は何ですか?返品値を決定するものは何ですか? Mar 03, 2025 pm 05:52 PM

この記事では、c関数のリターンタイプ、基本(int、float、charなど)、派生(配列、ポインター、構造体)、およびvoid型を含む詳細を示します。 コンパイラは、関数宣言とreturnステートメントを介して返品タイプを決定し、強制します

GULC:Cライブラリはゼロから構築されています GULC:Cライブラリはゼロから構築されています Mar 03, 2025 pm 05:46 PM

GULCは、最小限のオーバーヘッド、積極的なインライン、およびコンパイラの最適化を優先する高性能Cライブラリです。 高周波取引や組み込みシステムなどのパフォーマンスクリティカルなアプリケーションに最適な設計では、シンプルさ、モジュールが強調されています

C言語関数の定義と呼び出しルールは何ですか、そして C言語関数の定義と呼び出しルールは何ですか、そして Mar 03, 2025 pm 05:53 PM

この記事では、C関数宣言と定義、引数の合格(価値とポインターによる)、返品値、およびメモリリークやタイプの不一致などの一般的な落とし穴について説明します。 モジュール性とProviの宣言の重要性を強調しています

c言語関数形式文字ケース変換手順 c言語関数形式文字ケース変換手順 Mar 03, 2025 pm 05:53 PM

この記事では、文字列ケース変換のC関数について詳しく説明しています。 ctype.hのtoupper()とtolower()を使用し、文字列を介して繰り返し、ヌルターミネーターを処理することを説明しています。 ctype.hを忘れたり、文字列リテラルを変更するなどの一般的な落とし穴は

メモリに保存されているC言語関数の返品値はどこにありますか? メモリに保存されているC言語関数の返品値はどこにありますか? Mar 03, 2025 pm 05:51 PM

この記事では、C関数の戻り値ストレージを調べます。 通常、リターン値は通常、速度のためにレジスタに保存されます。値が大きいと、ポインターをメモリ(スタックまたはヒープ)に使用し、寿命に影響を与え、手動のメモリ管理が必要になります。直接acc

明確な使用法とフレーズ共有 明確な使用法とフレーズ共有 Mar 03, 2025 pm 05:51 PM

この記事では、形容詞の「個別」の多面的な使用法を分析し、その文法機能、一般的なフレーズ(例:「はっきりと異なる」とは異なる」、およびフォーマルと非公式の微妙なアプリケーションを調査します。

STL(ソート、検索、変換など)のアルゴリズムを効率的に使用するにはどうすればよいですか? STL(ソート、検索、変換など)のアルゴリズムを効率的に使用するにはどうすればよいですか? Mar 12, 2025 pm 04:52 PM

この記事では、cの効率的なSTLアルゴリズムの使用について詳しく説明しています。 データ構造の選択(ベクトル対リスト)、アルゴリズムの複雑さ分析(STD :: STD :: STD :: PARTIAL_SORTなど)、イテレーターの使用、および並列実行を強調しています。 のような一般的な落とし穴

C標準テンプレートライブラリ(STL)はどのように機能しますか? C標準テンプレートライブラリ(STL)はどのように機能しますか? Mar 12, 2025 pm 04:50 PM

この記事では、C標準テンプレートライブラリ(STL)について説明し、そのコアコンポーネント(コンテナ、イテレーター、アルゴリズム、およびファンクター)に焦点を当てています。 これらが一般的なプログラミングを有効にし、コード効率を向上させ、読みやすさを改善する方法を詳述しています。

See all articles