Tìm cặp giá trị dương/âm cùng giá trị tuyệt đối trong mảng bằng C++

Cho mảng các phần tử phân biệt. In các cặp (-x, x) cùng giá trị tuyệt đối, theo thứ tự tăng dần. 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

Cách vét cạn (Brute Force) O(N²)

Lồng hai vòng lặp, tìm cặp abs(arr[i]) == abs(arr[j]).

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);
    vector<int> nums;
    for(int i = 0; i < n; i++)
        for(int j = i+1; j < n; j++)
            if(abs(arr[j]) == abs(arr[i])) {
                nums.push_back(abs(arr[i]));
                break;
            }
    sort(nums.begin(), nums.end());
    for(auto x : nums) cout << -x << " " << x << " ";
}

Kết quả

-1 1 -12 12 -56 56

Cách hiệu quả: Hash Map O(N)

Dùng map đếm tần suất giá trị tuyệt đối. Giá trị nào có tần suất 2 → là cặp dương/âm. Map tự sắp xếp khóa → kết quả đã có thứ tự.

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);
    map<int, int> found;
    vector<int> nums;
    for(int i = 0; i < n; i++) found[abs(arr[i])]++;
    for(auto x : found) if (x.second == 2) nums.push_back(x.first);
    for(auto x : nums) cout << -x << " " << x << " ";
}

Kết quả

-1 1 -4 4 -8 8 -9 9

Kết luận

Tìm cặp dương/âm cùng giá trị tuyệt đối: Brute Force O(N²) và Hash Map O(N log N) (do map). Code C++ mẫu.