การหาคู่ค่าบวก-ลบ ในอาร์เรย์ โดยใช้ C++

ในบทความนี้ เรามีอาร์เรย์ที่มีองค์ประกอบที่แตกต่างกัน (distinct) เราต้องพิมพ์คู่ของค่าบวก-ลบ ในอาร์เรย์ที่มีค่าสัมบูรณ์เท่ากัน และพิมพ์พวกมันในลำดับที่จัดเรียงแล้ว ตัวอย่างเช่น:

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 approach และเราสร้างอีกวิธีหนึ่งชื่อ Efficient approach เราจะอภิปรายทั้งสองวิธี

วิธี 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); // ขนาดของอาร์เรย์
    vector 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;
                // ถ้าหาคู่เจอ เราสามารถ break ได้เลย เพราะมี distinct elements
            }
        }
    }
    sort(nums.begin(), nums.end());
    for(auto x : nums) // พิมพ์คู่
        cout << -x << " " << x << " ";
}

ผลลัพธ์

-1 1 -12 12 -56 56

ในวิธีนี้ เราใช้ลูปสองชั้นสำหรับเดินทางผ่านอาร์เรย์และหาองค์ประกอบอีกตัว ตอนนี้ถ้าเราหาองค์ประกอบอีกตัวเจอ เรา break ออกจาก inner loop เพื่อให้โค้ดทำงานเร็วขึ้น ตอนนี้เราใช้ for-loop สองชั้น ความซับซ้อนด้านเวลาทั้งหมดคือ O(N²) N คือขนาดของอาร์เรย์ที่กำหนด ซึ่งดีสำหรับข้อจำกัดต่ำ แต่ไม่ดีสำหรับข้อจำกัดสูง ดังนั้นตอนนี้เราจะอภิปรายวิธีอื่น

วิธีที่มีประสิทธิภาพ (Efficient Approach)

ในวิธีนี้ เราจะใช้ 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); // ขนาดของอาร์เรย์
    map found; // จะเก็บจำนวนที่พบ
    vector nums; // คู่ที่มีอยู่
    for(int i = 0; i < n; i++)
        found[abs(arr[i])]++; // เพิ่มความถี่ของ abs(arr[i])
    for(auto x : found) { // เดินทางผ่าน map
        if(x.second == 2) // ถ้าความถี่ของตัวเลขใดเป็น 2 ให้ push เข้า nums
            nums.push_back(x.first);
    }
    for(auto x : nums) // พิมพ์คู่
        cout << -x << " " << x << " ";
}

ผลลัพธ์

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

คำอธิบายโค้ด

ในวิธีนี้ เราใช้ hashmap เพื่อเก็บความถี่ของตัวเลข ขณะที่เราเดินทางผ่านอาร์เรย์ เรากำลังอัปเดตความถี่ของค่าสัมบูรณ์ขององค์ประกอบปัจจุบัน ตอนนี้คุณรู้ว่าคู่ทั้งหมดจะมีค่าเป็น 2 ดังนั้นเราจึงเดินทางผ่าน map ถ้าความถี่ของตัวเลขใดเป็น 2 เราก็เก็บมันไว้ใน nums และสุดท้ายเราพิมพ์ค่าในลำดับที่จัดเรียงแล้ว (เพราะ map มีตัวเลขในลำดับที่จัดเรียงแล้ว เราไม่ต้อง sort nums vector)

สรุป

ในบทความนี้ เราแก้ปัญหาการหาคู่ค่าบวก-ลบ ในอาร์เรย์โดยใช้ Hashing Technique เรายังเรียนรู้โปรแกรม C++ สำหรับปัญหานี้และวิธีการแก้ปัญหาแบบเต็มรูปแบบ (ธรรมดาและมีประสิทธิภาพ) ที่เราใช้แก้ปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, Java, Python และภาษาอื่นๆ ได้ เราหวังว่าบทความนี้จะเป็นประโยชน์