C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C ++でi

整数要素を含む配列が与えられます。目標は、型のペア（arr [i]、arr [j]）がi

のようなインデックスを持つように、配列の要素の一意のペアを見つけることです。

例を挙げて理解しましょう

入力 − arr [] ={1,2,3};

出力 − i となるような一意のペア（arr [i]、arr [j]）の数

説明 −すべての要素が一意であるため。ペアは-

になります 
(1,2) - ( arr[0],arr[1] ) 0<1
(1,3) - ( arr[0], arr[2] ) 0<2
(2,3) - ( arr[1],arr[2] ) 1<2

入力 − arr [] ={4,4,3,2};

出力 − i となるような一意のペア（arr [i]、arr [j]）の数

説明 −すべての要素が一意であるため。ペアは-

になります 
(4,4) - ( arr[0],arr[1] ) 0<1
(4,3) - ( arr[0], arr[2] ) 0<2
(4,2) - ( arr[0],arr[3] ) 0<3
(3,2) - ( arr[2],arr[3] ) 2<3

以下のプログラムで使用されているアプローチは次のとおりです

2つのアプローチを使用します。 forループを使用した最初の素朴なアプローチ。 2つのforループを使用して配列arr[]のトラバースを開始します。 i=0からi>seに追加します。 「se」の最後のサイズは、iとの一意のペアの数になります。

  • サイズとして整数要素と長さを持つ整数配列arr[]を取ります

  • 関数unique_pair（int arr []、int size）は、配列とその長さを受け取り、ペア（arr [i]、arr [j]）でインデックスi となるような一意のペアの数を返します。

  • countの初期値を0とします。

  • 整数のペアを含むセット「se」を取ります。 （set > se）

  • 2つのforループを使用してarr[]のトラバースを開始します。 i=0からi

  • 各ペアは常にiを使用してペア（arr [i]、arr [j]）を「se」に追加します。

  • 両方のforループの最後で、count =se.size（）を更新します。

  • Countには、「se」にいくつかのペアが含まれるようになりました。 （すべてが一意です。）

  • 結果としてカウントを返します。

効率的なアプローチ

このアプローチでは、各要素の後に一意の要素が見つかります。 arr [i]は、arr [i+1からsize-1]までの別個の/固有の要素とペアになります。したがって、arr [i]の後にx個の一意の要素がある場合、arr[i]はx個のペアを作成します。したがって、最初に、インデックスiの後に一意の要素をマークする配列を作成します。次に、そのようなカウントを個別に追加して、一意のペアの総数を求めます。

  • サイズとして整数要素と長さを持つ整数配列arr[]を取ります

  • 関数unique_pair（int arr []、int size）は、配列とその長さを受け取り、ペア（arr [i]、arr [j]）でインデックスi となるような一意のペアの数を返します。

  • countの初期値を0とします。

  • 一時変数を取得して0に設定します。

  • 長さサイズの配列arr_2[]を取得し、arr_2 [size-1] =0を初期化します。これは、最後の要素の後に一意の要素が0個あるためです。

  • チェックとチェック解除の2つの整数セットを作成します。

  • 最後の要素からfirst.i=size-1からi>=0まで配列をトラバースします。セットチェックでarr[i]を検索します。

  • 見つからない場合、それは一意です。 tempをインクリメントします（tempはarr [i]後の一意の要素の数です）。 arr_2 [i]=tempを設定します。

  • それ以外の場合、arr_2 [i]=temp。温度を上げずに

  • arr[i]を挿入してチェックを設定します。これで、arr[i]の次の発生は考慮されません。

  • このforループの終了後。 arr_2[]が更新されました。

  • ここで、arr[]をインデックスi=0からi

  • arr [i]を追加して、チェックを外します。これで、arr[i]の次の発生は考慮されません。

  • 最後に、カウントには一意のペアがあり、i

  • 結果としてカウントを返します。

例（素朴なアプローチ）

#include<bits/stdc++.h>
using namespace std;
int unique_pair(int arr[], int size){
   int count = 0;
   set<pair<int, int>> se;
   for(int i = 0; i < (size - 1); i++){
      for (int j = i + 1; j < size; j++){
         se.insert(make_pair(arr[i], arr[j]));
      }
   }
   count = se.size();
   return count;
}
int main(){
   int arr[] = { 4, 3, 1, 6, 7 };
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of unique pairs (arr[i], arr[j]) such that i < j are: "<<unique_pair(arr, size);
return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of unique pairs (arr[i], arr[j]) such that i & j are: 10

例（効率的なアプローチ）

#include<bits/stdc++.h>
using namespace std;
int unique_pair(int arr[], int size){
   int count = 0, temp = 0;
   int arr_2[size];
   arr_2[size-1] = 0;
   set<int> check, uncheck;
   for (int i = size - 1; i > 0; i--){
      auto set = check.find(arr[i]);
      if (set != check.end()){
         arr_2[i - 1] = temp;
      }
      else{
         arr_2[i - 1] = ++temp;
      }
      check.insert(arr[i]);
   }
   for (int i = 0; i < size - 1; i++){
      auto set = uncheck.find(arr[i]);
      if (set != uncheck.end()){
         continue;
      }
      count += arr_2[i];
      uncheck.insert(arr[i]);
   }
   return count;
}
int main(){
   int arr[] = { 4, 3, 1, 6, 7 };
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"Count of unique pairs (arr[i], arr[j]) such that i < j are: "<<unique_pair(arr, size);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of unique pairs (arr[i], arr[j]) such that i < j are: 10

  1. arr [j] – arr [i] + arr [l] – arr [k]を最大化し、C++でi<j<k<lになるようにします。

    整数の配列が与えられます。目標は、式の値を最大化することです- arr [j] -arr [i] + arr [l] -arr [k]; i

  2. C ++でa％b =kとなるような配列内のすべてのペア（a、b）を検索します

    配列Aがあるとすると、その配列から、a％b =kとなるようにすべてのペア（a、b）を取得する必要があります。配列がA=[2、3、4、5、7]、k =3であるとすると、ペアは（7、4）、（3、4）、（3、5）、（3、7）になります。 これを解決するために、リストをトラバースして、指定された条件が満たされているかどうかを確認します。 例 #include <iostream> using namespace std; bool displayPairs(int arr[], int n, int k) {    bool pairAvilable = true;