資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學使用 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 << " ";
}輸出
-1 1 -4 4 -8 8 -9 9
上述程式碼的解釋
在這種方法中，我們使用雜湊表來儲存數字的頻率；當我們遍歷陣列時，我們更新當前元素絕對值的頻率。眾所周知，所有對的頻率值都將為 2，然後我們遍歷該對映。
如果任何數字的頻率為 2，則將其儲存在 nums 中，最後我們按排序順序列印這些值。（由於對映包含按排序順序排列的數字，因此我們不需要對 numbers 向量進行排序）。
結論
在本文中，我們解決了一個使用雜湊技術查詢陣列中正負值對的問題。我們還學習了這個問題的 C++ 程式以及我們解決這個問題的完整方法（常規方法和高效方法）。我們可以使用 C、Java、Python 等其他語言編寫相同的程式。希望本文對您有所幫助。
更新於：2021年11月26日
瀏覽量：307
廣告