使用C++找到数组中的正负值对

王林转载: 2023-09-20 21:09:03 344浏览

使用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

寻找解决方案的方法

我们首先想到的方法是蛮力法，然后我们还想出了一种称为高效法的方法。我们将讨论这两种方法。

蛮力法

在这种方法中，我们将用一个索引遍历数组，并找到相同的绝对值但不同的索引。

示例

#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

在这种方法中，我们使用两个循环来遍历数组并找到另一个元素；如果我们找到另一个元素，我们会从内循环中跳出以加快代码运行速度。现在我们使用了两个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 << " ";
}