使用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;
}

輸出

Pair does not exist.

上述程式碼說明

• #聲明二維陣列並在其中儲存元素。
• 遍歷陣列尋找 if (sum - Matrix[i][j]) != hash.end()。
• 如果條件滿足，則列印「Pair contains」並從主函數返回。
• 否則，繼續遍歷數組，最後列印「 Pair does notise.」。

結論

在本文中，我們討論了在矩陣中尋找具有給定總和的對或二維數組；我們討論了解決這個問題的暴力方法和有效方法。我們討論了C 程式來解決這個問題。但是，我們可以用任何其他語言（例如 C、Java、Python 等）編寫此程式。我們希望本文對您有所幫助。

以上是使用C++編寫，在矩陣中找到給定和的一對數字的詳細內容。更多資訊請關注PHP中文網其他相關文章！