使用 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
寻找解决方案的方法
我们想到的第一种方法是BruteForce方法,我们又提出了另一种方法,称为Efficient方法。我们将讨论这两种方法。
蛮力方法
在这种方法中,我们将遍历具有一个索引的数组,并找到相同的绝对值但不同的索引。
示例
#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); //我们数组的大小。 vector<int> nums; //现在的对。 for(int i = 0; i < n; i++) { for(int j = i+1; j < n; j++) { if(abs(arr[j]) == abs(arr[i])) { //找到对。 nums.push_back(abs(arr[i])); break; //如果我们找到了这对,那么我们就可以打破,因为数组中有不同的元素。 } } } sort(nums.begin(), nums.end()); for(auto x : nums) //打印对。 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); //我们数组的大小。 map<int, int> found; //将存储找到的数字计数。 vector<int> nums; //现在的对。 for(int i = 0; i < n; i++) found[abs(arr[i])]++; //增加abs(arr[i])的频率。 for(auto x : found) { //穿越映射。 if(x.second == 2) //如果任何数字频率为2,则将其推至nums。 nums.push_back(x.first); } for(auto x : nums) //打印对。 cout << -x << " " << x << " "; }输出结果
-1 1 -4 4 -8 8 -9 9
上面代码的解释
在这种方法中,我们使用哈希图来存储数字的频率;当我们遍历数组时,我们正在更新当前元素的绝对值的频率,因为您知道所有对的值都为2,因此我们正在遍历映射。
如果任何数字的频率为2,那么我们将其存储在nums中,最后,我们将按排序顺序打印值。(由于映射包含按排序顺序排列的数字,我们不需要对数字向量进行排序)。
结论
在本文中,我们解决了使用哈希技术在数组中查找正负值对的问题。我们还学习了针对这个问题的C++程序以及我们解决这个问题的完整方法(普通和高效)。我们可以用其他语言编写相同的程序,例如C、java、python和其他语言。我们希望这篇文章对您有所帮助。