Trong bài toán này, chúng ta được cung cấp một mảng các số nguyên duy nhất. Và chúng ta phải trả về tất cả các cặp số nguyên (số nguyên dương và âm) có trong mảng.
Hãy lấy một ví dụ để hiểu rõ vấn đề hơn -
Input: array = {1 , 4 , 7 , -1, 2, 5, -7}
Output: -11 -33 Một cách dễ dàng để giải quyết vấn đề là sử dụng hai vòng lặp và tìm các cặp âm - dương. Nhưng giải pháp này sẽ là một giải pháp phức tạp và sẽ có độ phức tạp về thời gian theo thứ tự n2 trong đó n là kích thước của mảng.
Nhưng, chúng ta phải tìm ra một cách tiếp cận hiệu quả hơn để giải quyết vấn đề. Đối với điều đó, trước tiên chúng ta sẽ sắp xếp mảng. Và sau đó trong mảng đã sắp xếp này, với mọi số nguyên âm, hãy tìm số nguyên đối diện (dương). Tìm kiếm nhị phân này sẽ là một cách tiếp cận tốt. Và in các cặp được tìm thấy bằng cách sử dụng tìm kiếm.
Ví dụ
Hãy xem minh họa mã của phương pháp này -
#include <bits/stdc++.h>
using namespace std;
void positiveNegativePair(int arr[], int n) ;
int main(){
int arr[] = { 1, 4, 6 , 3, -1, -2, 5, -6, -5 , 8 };
int n = 10;
cout<<"Postive Negative pairs in the array are :\n";
positiveNegativePair(arr, n);
return 0;
}
void positiveNegativePair(int arr[], int n){
bool pair_exists = false;
sort(arr, arr + n);
for (int i = 0; i < n; i++) {
if (arr[i] < 0) {
if (binary_search(arr, arr + n, -arr[i])) {
cout<<arr[i]<<", "<<-arr[i]<<"\t";
pair_exists = true;
}
}
else
break;
}
if (!pair_exists)
cout << "No positive-negative pairs exist in the code";
} Đầu ra
Các cặp âm dương trong mảng là -
-6, 6 -5, 5 -1, 1