In C++ geschrieben, finden Sie ein Zahlenpaar in einer Matrix mit einer bestimmten Summe

In diesem Artikel besprechen wir das Programm zum Finden von Paaren mit einer bestimmten Summe in einer bestimmten Matrix. Zum Beispiel –

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.

Möglichkeiten, eine Lösung zu finden

Jetzt erklären wir zwei verschiedene Möglichkeiten, die Lösung für das oben genannte Problem zu finden.

Brute-Force-Methode

Betrachten Sie jedes Paar in der angegebenen Matrix und prüfen Sie, ob die Summe des Paares gleich der angegebenen SUMME ist. Wenn ja, geben Sie „Paar ist nicht“ aus. Andernfalls geben Sie „Paar ist nicht“ aus. Die Anwendung dieser Methode ist sehr einfach, erhöht jedoch die Zeitkomplexität auf O((N*M)2).

Effiziente Methode

Dieses Programm kann alle Matrixelemente mithilfe eines Hashs speichern, dann die Matrix durchlaufen und prüfen, ob die Differenzen von [SUMME & (Indexelement)] gleich sind. Wenn ja, geben Sie „Exist“ aus und beenden Sie das Programm. Wenn es NEIN ist, „existiert nicht“, nachdem der Druck durchlaufen wurde.

Beispiel

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

Ausgabe

Pair does not exist.

Die obige Codebeschreibung

• Deklarieren Sie ein zweidimensionales Array und speichern Sie Elemente darin.
• Durchlaufen Sie das Array, um herauszufinden, ob (sum - Matrix[i][j]) != hash.end().
• Wenn die Bedingung erfüllt ist, geben Sie „Paar enthält“ aus und kehren Sie von der Hauptfunktion zurück.
• Andernfalls durchqueren Sie das Array weiter und geben Sie schließlich „Pair notify“ aus.

Fazit

In diesem Artikel haben wir das Finden von Paaren oder 2D-Arrays mit einer bestimmten Summe in einer Matrix besprochen. Wir haben sowohl rohe Gewalt als auch effiziente Möglichkeiten zur Lösung dieses Problems besprochen. Wir haben ein C++-Programm zur Lösung dieses Problems besprochen. Wir können dieses Programm jedoch in jeder anderen Sprache wie C, Java, Python usw. schreiben. Wir hoffen, dass dieser Artikel für Sie hilfreich war.

Das obige ist der detaillierte Inhalt vonIn C++ geschrieben, finden Sie ein Zahlenpaar in einer Matrix mit einer bestimmten Summe. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!