使用 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
解决方法
我们首先想到的是暴力法,然后我们又提出了一种称为高效方法的方法。我们将讨论这两种方法。
暴力法
在这种方法中,我们将使用一个索引遍历数组,并查找具有相同绝对值但索引不同的元素。
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
示例
#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 << " "; }
输出
-1 1 -4 4 -8 8 -9 9
上述代码的解释
在这种方法中,我们使用哈希表来存储数字的频率;当我们遍历数组时,我们更新当前元素绝对值的频率。众所周知,所有对的频率值都将为 2,然后我们遍历该映射。
如果任何数字的频率为 2,则将其存储在 nums 中,最后我们按排序顺序打印这些值。(由于映射包含按排序顺序排列的数字,因此我们不需要对 numbers 向量进行排序)。
结论
在本文中,我们解决了一个使用哈希技术查找数组中正负值对的问题。我们还学习了这个问题的 C++ 程序以及我们解决这个问题的完整方法(常规方法和高效方法)。我们可以使用 C、Java、Python 等其他语言编写相同的程序。希望本文对您有所帮助。
广告