我们有一个阶数为N x M的矩阵,乘积为K。任务是检查矩阵中是否存在与给定乘积对。
假设矩阵如下-
1 | 2 | 3 | 4 |
5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 |
现在如果K为42,那么会有一对(6,7)
为了解决这个问题,我们将使用哈希。我们将通过获取矩阵的所有元素来创建哈希表。我们将开始遍历矩阵,同时遍历矩阵,检查矩阵的当前元素是否可被给定乘积整除,当乘积K除以当前元素时,被除数也将出现在哈希表中。所以要求的条件就像-
(k mod matrix [i,n])为假,哈希表具有k / matrix [i,j]
如果存在,则返回true,否则将当前元素插入哈希表。
如果找不到对,则返回false。
#include <iostream> #include <unordered_set> #define N 4 #define M 4 using namespace std; bool isPairPresent(int matrix[N][M], int K) { unordered_set<int> s; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if ((K % matrix[i][j] == 0) && (s.find(K / matrix[i][j]) != s.end())) { return true; } else { s.insert(matrix[i][j]); } } } return false; } int main() { int matrix[N][M] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}}; int k = 42; if (isPairPresent(matrix, k) == false) cout << "NO PAIR EXIST"; else cout << "Pair is present"; }
输出结果
Pair is present