数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
广告