Écrit en C++, trouver une paire de nombres dans une matrice avec une somme donnée

Dans cet article, nous discuterons du programme pour trouver des paires avec une somme donnée dans une matrice donnée. Par exemple -

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.

Façons de trouver une solution

Nous allons maintenant expliquer deux manières différentes de trouver la solution au problème ci-dessus.

Méthode de la Force Brute

Considérez chaque paire dans la matrice donnée, vérifiez si la somme de la paire est égale à la SOMME donnée, si c'est le cas, imprimez "La paire n'est pas" sinon, imprimez "La paire n'est pas". L'application de cette méthode est très simple, mais elle augmente la complexité temporelle à O((N*M)2).

Méthode efficace

Ce programme peut stocker tous les éléments de la matrice en utilisant le hachage, puis parcourir la matrice et vérifier si les différences de [SOMME & (élément d'index)] sont égales. Si tel est le cas, imprimez « Exist » et quittez le programme. Si c'est NON, "n'existe pas" après avoir traversé l'impression.

Exemple

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

Sortie

Pair does not exist.

La description du code ci-dessus

• Déclarez un tableau bidimensionnel et stockez-y des éléments.
• Parcourez le tableau pour trouver if (sum - Matrix[i][j]) != hash.end().
• Si la condition est remplie, imprimez "La paire contient" et revenez de la fonction principale.
• Sinon, continuez à parcourir le tableau et imprimez enfin "Pair notify.".

Conclusion

Dans cet article, nous avons discuté de la recherche de paires ou de tableaux 2D avec une somme donnée dans une matrice ; nous avons discuté à la fois de la force brute et des moyens efficaces pour résoudre ce problème. Nous avons discuté d'un programme C++ pour résoudre ce problème. Cependant, nous pouvons écrire ce programme dans n'importe quel autre langage comme C, Java, Python, etc. Nous espérons que cet article vous a été utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!