ในปัญหานี้ เราได้รับอาร์เรย์ของจำนวนเต็มที่ไม่ซ้ำกัน และเราต้องคืนค่าคู่ของจำนวนเต็ม (จำนวนเต็มบวกและลบ) ที่มีอยู่ในอาร์เรย์
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากันดีกว่า −
Input: array = {1 , 4 , 7 , -1, 2, 5, -7}
Output: -11 -33 วิธีง่ายๆ ในการแก้ปัญหาคือการใช้สองลูปและค้นหาคู่บวก-ลบ แต่วิธีแก้ปัญหานี้จะซับซ้อนและมีเวลาที่ซับซ้อนของลำดับ n2 โดยที่ n คือขนาดของอาร์เรย์
แต่เราต้องหาแนวทางที่มีประสิทธิภาพมากขึ้นในการแก้ปัญหา ก่อนอื่นเราจะเรียงลำดับอาร์เรย์ก่อน แล้วในอาร์เรย์ที่จัดเรียงนี้ สำหรับทุกจำนวนเต็มลบ ให้หาจำนวนเต็มตรงข้าม (บวก) การค้นหาแบบไบนารีนี้จะเป็นวิธีที่ดี และพิมพ์คู่ที่พบโดยใช้การค้นหา
ตัวอย่าง
มาดูภาพประกอบโค้ดของวิธีนี้กัน −
#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";
} ผลลัพธ์
คู่บวกเชิงลบในอาร์เรย์คือ -
-6, 6 -5, 5 -1, 1
