使用 C++ 在矩阵中查找具有给定总和的对
c++server side programmingprogramming
在本文中，我们将讨论在给定矩阵中查找具有给定总和的对的程序。例如 −
输入:matrix[n][m] = {
{ 4, 6, 4, 65 },
{ 56, 1, 12, 32 },
{ 4, 5, 6, 44 },
{ 13, 9, 11, 25 }
}, SUM = 20
输出:对存在。
解释:Sum = 20 等于矩阵中存在的数字 9 和 11 的总和。
输入:matrix[n][m] = {
{ 5, 7, 3, 45 },
{ 63, 5, 3, 7 },
{ 11, 6, 9, 5 },
{ 8, 6, 14, 15 }
}, SUM = 13
输出:对不存在。
解释:矩阵中不存在任何一对元素的和等于 7。
寻找解决方案的方法
现在我们将解释两种不同的方法来寻找上述问题的解决方案。
强力方法
考虑给定矩阵中的每一对元素，并检查该对元素的和是否等于给定的 SUM，如果是，则打印"对存在";否则，打印"对不存在"。应用这种方法非常简单，但时间复杂度将飙升至 O((N*M)2)。
高效方法
此程序可以通过使用哈希存储所有矩阵元素，然后遍历矩阵并检查 [ SUM & (索引元素) ] 的差是否相等来提高效率。如果是，则打印"存在"并退出程序。如果为NO，则遍历打印后，"不存在。"
示例
#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.
以上代码解释
- 声明二维数组并将元素存储在其中。
- 遍历数组查找 if (sum - matrix[i][j]) != hash.end()。
- 如果条件满足，则打印"Pair 存在"并从主函数返回。
- 否则，继续遍历数组并最终打印"对不存在。"
结论
在本文中，我们讨论了在矩阵或二维数组中查找具有给定和的对;我们讨论了解决这个问题的蛮力方法和有效方法。我们讨论了解决这个问题的 C++ 程序。但是，我们可以用任何其他语言(如 C、Java、Python 等)编写此程序。我们希望您觉得这篇文章有用。
