Cho mảng số nguyên duy nhất. In tất cả cặp (x, -x) cùng tồn tại trong mảng.
Input: array = {1, 4, 7, -1, 2, 5, -7} Output: -1 1 -7 7
Cách đơn giản: 2 vòng lặp O(n^2). Cách tốt: Sắp xếp mảng, với mỗi số âm dùng binary_search tìm số dương đối ứng.
Chương trình minh họa
#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 << "Các cặp dương âm trong mảng:\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 << "Không có cặp dương âm nào";
}
Kết quả
-6, 6 -5, 5 -1, 1