合計がC++の指定された値xに等しい2つのソートされた配列からペアをカウントします
正の数と値xを含む2つの配列が与えられます。目標は、タイプ(A、B)のペアがA + B =xであり、Aが最初の配列に属し、Bが2番目の配列に属するような配列の要素のペアを見つけることです。
例を挙げて理解しましょう
入力 − arr_1 [] ={1,2,5,3,4}; arr_2 [] ={7,0,1,3}; x =6
出力 −合計が指定された値xに等しい2つのソートされた配列からのペアの数は− 2
説明 −ペアは(5,1)-(arr_1 [2]、arr_2 [2])と(3,3)-(arr_1 [3]、arr_2 [3])
入力 − arr_1 [] ={1,1,1}; arr_2 [] ={2,2}; x =6
出力 −合計が指定された値xに等しい2つのソートされた配列からのペアの数は− 2
説明 −ペアは(1,2)-(arr_1 [0]、arr_2 [0])と(1,2)-(arr_1 [1]、arr_2 [1])
以下のプログラムで使用されているアプローチは次のとおりです
2つのアプローチを使用します。 forループを使用した最初の素朴なアプローチ。インデックスiがarr_1[]用で、インデックスjがarr_2 []用であるように、forループを使用して両方のトラバースを開始します。ペア(arr_1 [i] + arr_2 [j] ==x)の場合、カウントをインクリメントします。結果としてカウントを返します。
-
size_arr_1およびsize_arr_2として正の要素と長さを持つ整数配列arr_1[]およびarr_2[]を取ります。
-
関数Pair_value_x(int arr_1 []、int arr_2 []、int size_arr_1、int size_arr_2、int x)は、配列とその長さの両方を取り、要素の合計がxになるようにペアを返します。
-
countの初期値を0とします。
-
arr_1[]をi=0からi
にトラバースし始めます。 -
arr_1 [i]、arr_2 [j]のペアごとに、合計がxであるかどうかを確認します。 trueの場合、カウントをインクリメントします。
-
結果としてカウントを返します。
効率的なアプローチ
このアプローチでは、arr_1の要素のunordered_setを作成します。次に、forループと各値arr_2 [i]を使用してarr_2をトラバースします。セット内で、x-arr_2 [i]が見つかった場合は、カウントをインクリメントします。最後にカウントを返します。
-
同じアレイとそのサイズを使用します。
-
関数Pair_value_x(int arr_1 []、int arr_2 []、int size_arr_1、int size_arr_2、int x)は、配列とその長さの両方を取り、要素の合計がxになるようにペアを返します。
-
初期カウントを0とします。
-
arr_1の一意の要素を格納するためのunordered_set
hash_mapを作成します。 -
forループを使用してhash_mapにarr_1の要素を入力します。
-
次に、forループを使用してarr_2[]をトラバースします。
-
arr-2 [j]ごとに、(hash_map.find(x --arr_2 [j])!=hash_map.end())を使用してhash_mapでx-arr_2 [j]が見つかった場合は、カウントをインクリメントします。
-
最後に、合計がxに等しいペアとしてカウントします。
-
結果としてカウントを返します。
例(素朴なアプローチ)
#include <bits/stdc++.h> using namespace std; int Pair_value_x(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int x){ int count = 0; for (int i = 0; i < size_arr_1; i++){ for (int j = 0; j < size_arr_2; j++){ if ((arr_1[i] + arr_2[j]) == x){ count++; } } } return count; } int main(){ int arr_1[] = {1, 2, 3, 4}; int arr_2[] = {2, 3, 4, 5}; int size_arr_1 = sizeof(arr_1) / sizeof(arr_1[0]); int size_arr_2 = sizeof(arr_2) / sizeof(arr_2[0]); int x = 6; cout<<"Count of pairs from two sorted arrays whose sum is equal to a given value x are: "<< Pair_value_x(arr_1, arr_2, size_arr_1 , size_arr_2, x); return 0; }
出力
上記のコードを実行すると、次の出力が生成されます-
Count of pairs from two sorted arrays whose sum is equal to a given value x are: 4
例(効率的なアプローチ)
#include <bits/stdc++.h> using namespace std; int Pair_value_x(int arr_1[], int arr_2[], int size_arr_1, int size_arr_2, int x){ int count = 0; unordered_set<int> hash_map; for (int i = 0; i < size_arr_1; i++){ hash_map.insert(arr_1[i]); } for (int j = 0; j < size_arr_2; j++){ if (hash_map.find(x - arr_2[j]) != hash_map.end()){ count++; } } return count; } int main(){ int arr_1[] = {1, 2, 3, 4}; int arr_2[] = {2, 3, 4, 5}; int size_arr_1 = sizeof(arr_1) / sizeof(arr_1[0]); int size_arr_2 = sizeof(arr_2) / sizeof(arr_2[0]); int x = 6; cout<<"Count of pairs from two sorted arrays whose sum is equal to a given value x are: "<< Pair_value_x(arr_1, arr_2, size_arr_1 , size_arr_2, x); return 0; }
出力
上記のコードを実行すると、次の出力が生成されます-
Count of pairs from two sorted arrays whose sum is equal to a given value x are: 4
-
ソートされた二重リンクリスト内のトリプレットをカウントします。このリストの積は、C++で指定された値xに等しくなります。
整数値を含むソートされた二重リンクリストが与えられます。目標は、積が与えられた値xに等しいトリプレットを見つけることです。入力リンクリストが3−4−1−2で、xが6の場合、カウントは1になります(トリプレット(3,1,2)) 例 入力 linked list: [ 200−4−16−5−10−10−2 ] x=200 出力 Count of triplets in a sorted doubly linked list whose product is equal to a given value x are:
-
合計がC++の指定された値xに等しい2つのBSTからペアをカウントします
入力として2つの二分探索木と変数xが与えられます。目標は、ノードの値の合計がxに等しくなるように、各ツリーからノードのペアを見つけることです。 BST_1からノード1を取得し、BST_2からノード2を取得して、両方のデータ部分を追加します。 sum=xの場合。インクリメントカウント。 例を挙げて理解しましょう。 入力 出力 −合計が特定の値xに等しい2つのBSTからのペアの数は− 1 説明 −ペアは(8,6) 入力 出力 −合計が特定の値xに等しい2つのBSTからのペアの数は− 2 説明 −ペアは(5,15)と(4,16) 以下のプログラムで使用されているアプ