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 などの他の言語で書くことができます。この記事がお役に立てば幸いです。

以上がC++ を使用して配列内の正の値と負の値のペアを検索しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。