ホームページ  >  記事  >  バックエンド開発  >  左側のすべての要素よりも大きく、右側に少なくとも K 個の要素がある配列要素の数を数える C++ プログラム

左側のすべての要素よりも大きく、右側に少なくとも K 個の要素がある配列要素の数を数える C++ プログラム

WBOY
WBOY転載
2023-09-18 18:17:06922ブラウズ

左側のすべての要素よりも大きく、右側に少なくとも K 個の要素がある配列要素の数を数える C++ プログラム

#文字列は、一連のデータ文字を表すオブジェクトです。文字列は、常にテキスト形式で表されるデータ コンテナです。また、概念、比較、分割、結合、置換、トリム、長さ、インターニング、等価、比較、部分文字列の操作にも使用されます。クイックソート分割アルゴリズムを使用した、配列内の K 個の最大 (または最小) 要素。

これは、N 個の異なる整数を含む配列 R[] です。タスクは、その前のすべての要素よりも厳密に大きく、その右側の少なくとも K 要素よりも厳密に大きい特定の要素を見つけることです。質問では、配列 arr[ ] (配列 R) は N 個の異なる要素と整数 K で構成されていると述べています。左側のすべての要素より大きく、右側に少なくとも K 個の要素がある要素の数を見つけなければなりません。 。

リーリー

左側のすべての要素よりも大きい配列要素、および右側の少なくとも K 個の要素よりも大きい配列要素を見つける方法は 2 つあります。

  • 単純な方法 - これは、特定の配列を反復処理する最も簡単な方法です。このメソッドでは、要素が小さいかどうかを確認するために、すべての要素を左側に移動する必要があります。それ以外の場合は、右にトラバースして、最小の K 要素がより小さいかどうかを確認します。このアプローチの場合、時間計算量は O(N2)、補助空間は O(1) です。

  • 効率的な方法 - これは、自己バランス型 BST を使用して実行できる最適化プロセスです。 AVL ツリーを右から左に 1 つずつ配列をトラバースします。 AVL ツリーは配列 countSmaller[] を生成します。ここで、時間計算量は O(NlogN)、補助空間は O(N) です。条件を満たす要素ごとに、カウントが増加します。

左側のすべての要素と右側の少なくとも K 個の要素よりも大きい配列要素の数を見つけてみましょう。

すべての要素より大きい配列要素を計算するためのアルゴリズム:-

このアルゴリズムでは、段階的なプロセスに従って配列要素の数を数えます。これを使用して、すべての要素の中から最大の要素を見つけるための C コードを構築します。

  • ステップ 1 - 始めましょう。

  • ステップ 2 - 配列を右から左に走査します。

  • ステップ 3 - すべての要素を AVL ツリーに挿入します。

  • ステップ 4 - AVL ツリーを使用して配列 countSmaller[] を生成します。

  • ステップ 5 - これには、各配列要素の右側にある小さい要素の数が含まれます。

  • ステップ 6 - 配列をループし、各要素を見つけます。

  • ステップ 7 - これがこれまでに取得した最大値であるかどうか、および countSmaller[i] が K 以上で​​あるかどうかを確認します。

  • ステップ 8 - 条件が満たされる場合、カウントを増やします。

  • ステップ 9 - count の最終値を答えとして出力します。

  • ステップ 10 - 終了。

  • ###文法### リーリー
ここに整数配列 num があります。整数は K です。配列内の K 番目の要素を返します。 O(n) 時間の計算量でそれを解決する必要があります。

###方法###

方法 1 - 並べ替えを使用して K 個の最大 (または最小) 要素を見つけます。

  • 方法 2 - 配列内の K 個の最大 (または最小) 要素を見つける効率的な方法。

  • 並べ替えを使用して K 個の最大 (または最小) 要素を検索します

    この問題の結果はソートすることで得られます。手順は次のとおりです -

要素を降順に並べ替えます。

  • ソートされた配列の最初の K 個の数値を出力します。

  • 例 1

    リーリー ###出力### リーリー

    配列内の K 個の最大 (または最小) 要素を見つける効率的な方法
このメソッドでは、次の手順に従って結果を確認します -

######始める。

配列を右から左に走査します。

  • AVL ツリーにすべての要素を挿入します。

  • 配列 countSmaller[] を生成します。

  • 各配列要素の右側にある小さい要素の数。

  • 最大値の場合、countSmaller[i]はK以上です。

  • 次に、カウントをインクリメントします。

  • 値を出力します。

    ######仕上げる。
  • 例 2
  • リーリー ###出力### リーリー ###結論は###
  • これで、左側のすべての要素と右側の K 個以上の要素よりも大きい配列要素の数をカウントする C コードを記述する方法がわかりました。

以上が左側のすべての要素よりも大きく、右側に少なくとも K 個の要素がある配列要素の数を数える C++ プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事はtutorialspoint.comで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。