Trong bài này, chúng ta có một mảng chứa các phần tử riêng biệt. Chúng ta cần in các cặp giá trị âm - dương trong mảng có cùng giá trị tuyệt đối và in chúng theo thứ tự đã sắp xếp cho các ví dụ -
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 Phương pháp tiếp cận để tìm ra giải pháp
Cách tiếp cận đầu tiên xuất hiện trong đầu chúng tôi là phương pháp Brute Force, và chúng tôi tạo ra một phương pháp khác gọi là phương pháp Hiệu quả. Chúng ta sẽ thảo luận về cả hai cách tiếp cận.
Phương pháp tiếp cận vũ phu
Trong cách tiếp cận này, chúng tôi sẽ duyệt qua mảng với một chỉ mục trong tay và tìm cùng một giá trị tuyệt đối nhưng khác một chỉ mục.
Ví dụ
#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 << " ";
} Đầu ra
-1 1 -12 12 -56 56
Trong cách tiếp cận này, chúng tôi sử dụng hai vòng lặp để duyệt qua mảng và tìm phần tử khác ngay bây giờ; nếu chúng tôi tìm thấy phần tử khác, chúng tôi thoát ra khỏi vòng lặp bên trong để chạy mã nhanh hơn. Bây giờ chúng ta đang sử dụng hai vòng lặp for, độ phức tạp thời gian tổng thể của chúng ta là O (N * N). N là kích thước của một mảng nhất định phù hợp với các ràng buộc thấp hơn nhưng không tốt cho các ràng buộc cao hơn, vì vậy bây giờ chúng ta sẽ thảo luận về cách tiếp cận khác.
Phương pháp tiếp cận hiệu quả
Trong cách tiếp cận này, chúng tôi sẽ sử dụng một bản đồ băm, sẽ giúp giảm đáng kể sự phức tạp về thời gian của chúng tôi.
Ví dụ
#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 << " ";
} Đầu ra
-1 1 -4 4 -8 8 -9 9
Giải thích về đoạn mã trên
Trong cách tiếp cận này, chúng tôi đang sử dụng một bản đồ băm để lưu trữ tần suất của một số; khi chúng tôi duyệt qua mảng, chúng tôi đang cập nhật tần suất của giá trị tuyệt đối của phần tử hiện tại vì bạn biết rằng tất cả các cặp sẽ có giá trị là hai, vì vậy chúng tôi đang duyệt qua bản đồ.
Nếu tần suất của bất kỳ số nào là 2, thì chúng ta đang lưu trữ nó dưới dạng nums và cuối cùng, chúng ta đang in các giá trị theo thứ tự đã sắp xếp. (vì bản đồ chứa số theo thứ tự được sắp xếp, chúng tôi không cần sắp xếp vectơ số).
Kết luận
Trong bài viết này, chúng tôi giải quyết một vấn đề để tìm các cặp giá trị âm dương trong một mảng bằng cách sử dụng kỹ thuật băm. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường và hiệu quả) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy bài viết này hữu ích.