使用C++编写，在矩阵中找到给定和的一对数字-C++-PHP中文网

使用C++编写，在矩阵中找到给定和的一对数字

WBOY

发布： 2023-09-09 18:05:02

转载

1392 人浏览过

使用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，如果是，则打印“Pair isn't”；否则，打印“配对不存在”。应用这种方法非常简单，但它会将时间复杂度提高到 O((N*M)2)。

高效方法

该程序可以通过使用hash存储所有矩阵元素，然后遍历矩阵并检查[ SUM & (index element) ]的差值是否相等。如果是，则打印“Exist”并退出程序。如果为NO，则遍历print后，“不存在”。

示例

#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;
}

登录后复制