Trong bài này, chúng ta sẽ thảo luận về chương trình tìm một cặp với một tổng cho trước trong một ma trận cho trước. Ví dụ -
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. Phương pháp tiếp cận để tìm ra giải pháp
Bây giờ chúng tôi sẽ giải thích hai cách tiếp cận khác nhau để tìm ra giải pháp cho vấn đề trên.
Phương pháp tiếp cận vũ phu
Xem xét từng cặp trong ma trận đã cho và kiểm tra xem tổng của cặp đó có bằng SUM đã cho hay không, nếu có, sau đó in “Cặp tồn tại”; nếu không, hãy in “Cặp không tồn tại.” Áp dụng phương pháp này rất đơn giản, nhưng nó sẽ làm tăng độ phức tạp về thời gian lên O ((N * M) 2).
Phương pháp tiếp cận hiệu quả
Chương trình này có thể hiệu quả bằng cách sử dụng hàm băm để lưu trữ tất cả các phần tử của ma trận và sau đó duyệt qua ma trận và kiểm tra xem sự khác biệt của [SUM &(phần tử chỉ số)] có bằng nhau hay không. Nếu CÓ, sau đó In “Tồn tại” và thoát khỏi chương trình. Nếu KHÔNG, thì sau khi duyệt qua bản in, "không tồn tại."
Ví dụ
#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;
} Đầu ra
Pair does not exist.
Giải thích về đoạn mã trên
- Khai báo mảng 2-D và lưu trữ các phần tử trong đó.
- Duyệt qua mảng tìm kiếm if (sum - matrix [i] [j])! =hash.end ().
- Nếu điều kiện thỏa mãn, sau đó in "Có tồn tại cặp" và trả về từ hàm chính.
- Nếu không, hãy tiếp tục duyệt qua mảng và cuối cùng in ra “Cặp không tồn tại.”
Kết luận
Trong bài viết này, chúng ta đã thảo luận về việc tìm một cặp có tổng cho trước trong ma trận hoặc mảng 2-D; Chúng tôi đã thảo luận về cách tiếp cận Brute-force và một cách tiếp cận Hiệu quả để giải quyết vấn đề này. Chúng tôi đã thảo luận về chương trình C ++ để giải quyết vấn đề này. Tuy nhiên, chúng tôi có thể viết chương trình này bằng bất kỳ ngôn ngữ nào khác như C, Java, Python, v.v. Chúng tôi hy vọng bạn thấy bài viết này hữu ích.