ค้นหาคู่ที่มียอดรวมในเมทริกซ์โดยใช้ C++

ในบทความนี้ เราจะพูดถึงโปรแกรมการหาคู่ด้วยผลรวมที่กำหนดในเมทริกซ์ที่กำหนด ตัวอย่างเช่น −

Input : matrix[n][m] = { 
   { 4, 6, 4, 65 }, 
   { 56, 1, 12, 32 },
   { 4, 5, 6, 44 },
   { 13, 9, 11, 25 } 
}, SUM = 20

Output : Pair exists.
Explanation : Sum = 20 is equal to the sum of numbers 9 and 11 which exists in the matrix.

Input : matrix[n][m] = { 
   { 5, 7, 3, 45 },  
   { 63, 5, 3, 7 },  
   { 11, 6, 9, 5 },
   { 8, 6, 14, 15 } 
}, SUM = 13
Output : Pair does not exist.
Explanation : No pair exists in the matrix whose sum is equal to 7.

แนวทางในการหาทางออก

ตอนนี้เราจะอธิบายวิธีการที่แตกต่างกันสองวิธีเพื่อค้นหาวิธีแก้ไขปัญหาข้างต้น

แนวทางเดรัจฉาน

พิจารณาแต่ละคู่ในเมทริกซ์ที่กำหนดและตรวจสอบว่าผลรวมของคู่นั้นเท่ากับ SUM ที่กำหนดหรือไม่ ถ้าใช่ ให้พิมพ์ว่า "มีคู่อยู่" มิฉะนั้น พิมพ์ “ไม่มีคู่” การใช้วิธีนี้ทำได้ง่ายมาก แต่จะเพิ่มความซับซ้อนของเวลาเป็น O((N*M)2)

แนวทางที่มีประสิทธิภาพ

โปรแกรมนี้สามารถมีประสิทธิภาพได้โดยใช้แฮชเพื่อเก็บองค์ประกอบเมทริกซ์ทั้งหมด จากนั้นข้ามผ่านเมทริกซ์และตรวจสอบว่าผลต่างของ [ SUM &(องค์ประกอบดัชนี) ] เท่ากันหรือไม่ ถ้าใช่ ให้พิมพ์ Exist และออกจากโปรแกรม หากไม่ จากนั้นหลังจากผ่านการพิมพ์แล้ว “ไม่มีอยู่จริง”

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

#define n 4
#define m 4

int main() {
   int matrix[n][m] = { 
      { 5,7, 3,45 },
      { 63, 5, 3, 7 },
      { 11, 6, 9, 5 },
      { 8, 6, 14, 15 } 
   };

   int sum = 7;
   unordered_set<int> hash;

   for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
         if (hash.find(sum - matrix[i][j]) != hash.end()) {
            cout << "Pair exists." << endl;
            return 0;
         } else {
            hash.insert(matrix[i][j]);
         }
      }
   }

   cout << "Pair does not exist." << endl;
   return 0;
}

ผลลัพธ์

Pair does not exist.

คำอธิบายของโค้ดด้านบน

• การประกาศอาร์เรย์ 2 มิติและการจัดเก็บองค์ประกอบในนั้น
• การข้ามผ่านอาร์เรย์พบว่า (ผลรวม - matrix[i][j]) !=hash.end()
• หากตรงตามเงื่อนไข ให้พิมพ์ "Pair มี" และส่งคืนจากฟังก์ชันหลัก
• มิฉะนั้น ให้สำรวจอาร์เรย์ไปเรื่อยๆ และสุดท้ายพิมพ์ว่า "ไม่มีคู่"

บทสรุป

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