ในบทความนี้ เรามีอาร์เรย์ที่มีองค์ประกอบที่แตกต่างกัน เราจำเป็นต้องพิมพ์คู่ของค่าบวก-ลบในอาร์เรย์ที่มีค่าสัมบูรณ์เดียวกันและพิมพ์ตามลำดับสำหรับตัวอย่าง -
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 แนวทางในการหาทางออก
แนวทางแรกที่เข้ามาในความคิดของเราคือแนวทาง Brute Force และเราได้สร้างแนวทางใหม่ที่เรียกว่าแนวทางที่มีประสิทธิภาพ เราจะหารือเกี่ยวกับแนวทางทั้งสองนี้
แนวทางกำลังเดรัจฉาน
ในแนวทางนี้ เราจะสำรวจอาร์เรย์ด้วยดัชนีเดียวและค้นหาค่าสัมบูรณ์เดียวกันแต่เป็นดัชนีอื่น
ตัวอย่าง
#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); // size of our array.
vector<int> nums; // the present pairs.
for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
if(abs(arr[j]) == abs(arr[i])) { // finding the pairs.
nums.push_back(abs(arr[i]));
break;
// if we found the pair then we can just break as there are distinct elements in the array.
}
}
}
sort(nums.begin(), nums.end());
for(auto x : nums) // printing the pairs.
cout << -x << " " << x << " ";
} ผลลัพธ์
-1 1 -12 12 -56 56
ในแนวทางนี้ เราใช้สองลูปเพื่อสำรวจอาร์เรย์และค้นหาองค์ประกอบอื่นในขณะนี้ หากเราพบองค์ประกอบอื่น เราจะแยกตัวออกจากวงในเพื่อเรียกใช้โค้ดได้เร็วขึ้น ตอนนี้เราใช้สอง for-loop ความซับซ้อนของเวลาโดยรวมของเราคือ O(N*N) N คือขนาดของอาร์เรย์ที่กำหนดซึ่งดีสำหรับข้อจำกัดที่ต่ำกว่า แต่ไม่ดีสำหรับข้อจำกัดที่สูงกว่า ดังนั้นตอนนี้เราจะหารือเกี่ยวกับแนวทางอื่น
แนวทางที่มีประสิทธิภาพ
ในแนวทางนี้ เราจะใช้ hashmap ซึ่งจะช่วยลดความซับซ้อนของเวลาได้อย่างมาก
ตัวอย่าง
#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); // size of our array.
map<int, int> found; // going to store the count of numbers found.
vector<int> nums; // the present pairs.
for(int i = 0; i < n; i++)
found[abs(arr[i])]++; // increasing the frequency of abs(arr[i]).
for(auto x : found) { // traversing the map.
if(x.second == 2) // if any numbers frequency is two then push it to nums.
nums.push_back(x.first);
}
for(auto x : nums) // printing the pairs.
cout << -x << " " << x << " ";
} ผลลัพธ์
-1 1 -4 4 -8 8 -9 9
คำอธิบายของโค้ดด้านบน
ในแนวทางนี้ เราใช้ hashmap เพื่อเก็บความถี่ของตัวเลข ขณะที่เราสำรวจผ่านอาร์เรย์ เรากำลังอัปเดตความถี่ของค่าสัมบูรณ์ขององค์ประกอบปัจจุบัน เนื่องจากคุณทราบแล้วว่าทุกคู่มีค่าเท่ากับสอง ดังนั้นเรากำลังสำรวจแผนที่
หากความถี่ของตัวเลขใด ๆ เป็น 2 แสดงว่าเรากำลังจัดเก็บเป็น num และสุดท้าย เรากำลังพิมพ์ค่าตามลำดับการจัดเรียง (เนื่องจากแผนที่มีตัวเลขตามลำดับ เราจึงไม่จำเป็นต้องจัดเรียงเวกเตอร์ตัวเลข)
บทสรุป
ในบทความนี้ เราจะแก้ปัญหาเพื่อค้นหาคู่ค่าลบที่เป็นบวกในอาร์เรย์โดยใช้เทคนิคการแฮช นอกจากนี้เรายังได้เรียนรู้โปรแกรม C ++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ ( Normal และ มีประสิทธิภาพ ) โดยที่เราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทความนี้มีประโยชน์
