พิมพ์คู่ที่มีค่าบวกและลบขององค์ประกอบเดียวกันใน C++

ในปัญหานี้ เราจะได้รับ array ของจำนวนเต็มที่ไม่ซ้ำกัน และต้องคืนค่าคู่ของจำนวนเต็มทั้งหมด (จำนวนเต็มบวกและลบ) ที่มีอยู่ใน array

ตัวอย่างเพื่อความเข้าใจ

Input: array = {1, 4, 7, -1, 2, 5, -7}
Output: -1 1 -3 3

วิธีง่ายคือใช้ 2 loops หา positive-negative pairs แต่จะซับซ้อนและ time complexity เป็น O(n²)

แต่เราต้องหาวิธีที่มีประสิทธิภาพมากกว่า สำหรับนั้น เราจะ sort array ก่อน แล้วใน sorted array นี้ สำหรับทุก negative integer ให้หา opposite (positive) integer ด้วย binary search วิธีนี้ดีกว่า และพิมพ์คู่ที่พบ

โปรแกรมตัวอย่าง

#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 << "Positive 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";
}

ผลลัพธ์

Positive Negative pairs in the array are -

-6, 6 -5, 5 -1, 1