在本文中,我們將討論在給定矩陣中尋找具有給定和的對的程式。例如 -
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.
在本文中,我們討論了在矩陣中尋找具有給定總和的對或二維數組;我們討論了解決這個問題的暴力方法和有效方法。我們討論了C 程式來解決這個問題。但是,我們可以用任何其他語言(例如 C、Java、Python 等)編寫此程式。我們希望本文對您有所幫助。
以上是使用C++編寫,在矩陣中找到給定和的一對數字的詳細內容。更多資訊請關注PHP中文網其他相關文章!