資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 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 & (索引元素) ] 的差值是否相等，可以使此程式更高效。如果是，則列印“存在”並退出程式。如果不是，則在遍歷後列印“不存在”。
示例
#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.
上述程式碼的解釋
- 宣告二維陣列並在其中儲存元素。
- 遍歷陣列，查詢 (sum - matrix[i][j]) != hash.end() 是否成立。
- 如果條件滿足，則列印“配對存在”並從主函式返回。
- 否則，繼續遍歷陣列，最後列印“配對不存在”。
結論
在本文中，我們討論了在矩陣或二維陣列中查詢具有給定和的配對；我們討論了蠻力法和一種高效方法來解決此問題。我們討論了用 C++ 編寫的程式來解決此問題。但是，我們也可以用其他任何語言（如 C、Java、Python 等）編寫此程式。希望本文對您有所幫助。
更新於: 2021年11月26日
216 次檢視
廣告