C ++を使用して、配列内の正の負の値のペアを検索します

この記事では、個別の要素を含む配列があります。配列内の正と負の値のペアを同じ絶対値で出力し、例としてソートされた順序で出力する必要があります-

Input : arr[] = { 1, -1, 11, 12, 56, 77, -56, -12, -88}
Output : -1 1 -12 12 -56 56

Input : arr[] = {30, 40, 50, 77, -51, -50, -40}
Output : -40 40 -50 50

解決策を見つけるためのアプローチ

私たちの頭に浮かぶ最初のアプローチはブルートフォースアプローチであり、私たちは効率的なアプローチと呼ばれる別のアプローチを作り上げています。両方のアプローチについて説明します。

ブルートフォースアプローチ

このアプローチでは、1つのインデックスを使用して配列をトラバースし、同じ絶対値であるが異なるインデックスを見つけます。

例

#include<bits/stdc++.h>
using namespace std;

int main() {
   int arr[] = { 1, -1, 11, 12, 56, 77, -56, -12, -88 };
   int n = sizeof(arr)/sizeof(int); // size of our array.
   vector<int> nums; // the present pairs.

   for(int i = 0; i < n; i++) {
      for(int j = i+1; j < n; j++) {
         if(abs(arr[j]) == abs(arr[i])) { // finding the pairs.
            nums.push_back(abs(arr[i]));
            break;
            // if we found the pair then we can just break as there are distinct elements in the array.
         }
      }
   }
   sort(nums.begin(), nums.end());
   for(auto x : nums) // printing the pairs.
      cout << -x << " " << x << " ";
}

出力

-1 1 -12 12 -56 56

このアプローチでは、配列をトラバースして他の要素を見つけるために2つのループを使用します。他の要素が見つかった場合は、内側のループから抜け出し、コードをより高速に実行します。 2つのforループを使用しているので、全体的な時間計算量はO（N * N）です。 Nは特定の配列のサイズであり、低い制約には適していますが、高い制約には適していないため、他のアプローチについて説明します。

効率的なアプローチ

このアプローチでは、ハッシュマップを使用します。これにより、時間の複雑さが大幅に軽減されます。

例

#include<bits/stdc++.h>
using namespace std;
int main() {
   int arr[] = { 4, 8, 9, -4, 1, -1, -8, -9 };
   int n = sizeof(arr)/sizeof(int); // size of our array.
   map<int, int> found; // going to store the count of numbers found.
   vector<int> nums; // the present pairs.
   for(int i = 0; i < n; i++)
      found[abs(arr[i])]++; // increasing the frequency of abs(arr[i]).
   for(auto x : found) { // traversing the map.
      if(x.second == 2) // if any numbers frequency is two then push it to nums.
         nums.push_back(x.first);
   }
   for(auto x : nums) // printing the pairs.
      cout << -x << " " << x << " ";
}

出力

-1 1 -4 4 -8 8 -9 9

上記のコードの説明

このアプローチでは、ハッシュマップを使用して数値の頻度を格納しています。配列をトラバースすると、現在の要素の絶対値の頻度が更新されます。これは、すべてのペアの値が2になることがわかっているため、マップをトラバースしています。

任意の数値の頻度が2の場合、それをnumsで格納し、最後に、ソートされた順序で値を出力します。 （マップには並べ替えられた順序で番号が含まれているため、番号ベクトルを並べ替える必要はありません）。

結論

この記事では、ハッシュ手法を使用して配列内の正の負の値のペアを見つけるための問題を解決します。また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチ（通常および効率的）についても学びました。同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。この記事がお役に立てば幸いです。