Se dice que dos pares (a, b) y (c, d) son simétricos si c es igual a b ya es igual a d. Por ejemplo, (10, 20) y (20, 10) son simétricos. Dada una array de pares, encuentre todos los pares simétricos en ella.
Puede suponerse que los primeros elementos de todos los pares son distintos.
Ejemplo:
Input: arr[] = {{11, 20}, {30, 40}, {5, 10}, {40, 30}, {10, 5}}
Output: Following pairs have symmetric pairs
(30, 40)
(5, 10)
Enfoque ingenuo: la idea es usar dos bucles anidados, uno para seleccionar un par y el segundo para buscar el otro par simétrico en la array dada.
Se dice que el par es simétrico si arr[i][0] == arr[j][1] y arr[i][1] == arr[j][0] satisfacen.
A continuación se muestra la implementación del enfoque anterior:
C++
// A C++ program to find all symmetric pairs in a given
// array of pairs
#include <bits/stdc++.h>
using namespace std;
void findSymPairs(int arr[][2], int row)
{
// This loop for selection of one pair
for (int i = 0; i < row; i++) {
// This loop for searching of symmetric pair
for (int j = i + 1; j < row; j++) {
// Condition of symmetric pair
if (arr[i][0] == arr[j][1]
and arr[i][1] == arr[j][0])
{
cout << "(" << arr[i][0] << ", "
<< arr[i][1] << ")" << endl;
}
}
}
}
// Driver method
int main()
{
int arr[5][2];
arr[0][0] = 11;
arr[0][1] = 20;
arr[1][0] = 30;
arr[1][1] = 40;
arr[2][0] = 5;
arr[2][1] = 10;
arr[3][0] = 40;
arr[3][1] = 30;
arr[4][0] = 10;
arr[4][1] = 5;
cout << "Following pairs have symmetric pairs\n";
findSymPairs(arr, 5);
}
// This is contributed by Arpit Jain
Java
public class GFG
{
// A Java program to find all symmetric pairs in a given
// array of pairs
public static void findSymPairs(int[][] arr, int row)
{
// This loop for selection of one pair
for (int i = 0; i < row; i++) {
// This loop for searching of symmetric pair
for (int j = i + 1; j < row; j++) {
// Condition of symmetric pair
if (arr[i][0] == arr[j][1]
&& arr[i][1] == arr[j][0]) {
System.out.print("(");
System.out.print(arr[i][0]);
System.out.print(", ");
System.out.print(arr[i][1]);
System.out.print(")");
System.out.print("\n");
}
}
}
}
// Driver method
public static void main(String[] args)
{
int[][] arr = new int[5][2];
arr[0][0] = 11;
arr[0][1] = 20;
arr[1][0] = 30;
arr[1][1] = 40;
arr[2][0] = 5;
arr[2][1] = 10;
arr[3][0] = 40;
arr[3][1] = 30;
arr[4][0] = 10;
arr[4][1] = 5;
System.out.print(
"Following pairs have symmetric pairs\n");
findSymPairs(arr, 5);
}
}
// This is contributed by Aarti_Rathi
C#
using System;
public class GFG
{
// A C# program to find all symmetric pairs in a given
// array of pairs
public static void findSymPairs(int[,] arr, int row)
{
// This loop for selection of one pair
for (int i = 0; i < row; i++) {
// This loop for searching of symmetric pair
for (int j = i + 1; j < row; j++) {
// Condition of symmetric pair
if (arr[i,0] == arr[j,1]
&& arr[i,1] == arr[j,0]) {
Console.Write("(");
Console.Write(arr[i,0]);
Console.Write(", ");
Console.Write(arr[i,1]);
Console.Write(")");
Console.Write("\n");
}
}
}
}
// Driver method
public static void Main(String[] args)
{
int[,] arr = new int[5,2];
arr[0,0] = 11;
arr[0,1] = 20;
arr[1,0] = 30;
arr[1,1] = 40;
arr[2,0] = 5;
arr[2,1] = 10;
arr[3,0] = 40;
arr[3,1] = 30;
arr[4,0] = 10;
arr[4,1] = 5;
Console.Write(
"Following pairs have symmetric pairs\n");
findSymPairs(arr, 5);
}
}
// This is contributed by Abhijeet Kumar(abhijeet19403)
Following pairs have symmetric pairs (30, 40) (5, 10)
Complejidad temporal: O(n 2 ) .
Espacio Auxiliar: O(1)
Una mejor solución es utilizar la clasificación. Ordena todos los pares por el primer elemento. Para cada par, haga una búsqueda binaria del segundo elemento en la array dada, es decir, verifique si el segundo elemento de este par existe como el primer elemento en la array. Si lo encuentra, compare el primer elemento del par con el segundo elemento. La complejidad temporal de esta solución es O(nLogn) .
Una solución eficiente es usar Hashing. El primer elemento del par se usa como clave y el segundo elemento se usa como valor. La idea es atravesar todos los pares uno por uno. Para cada par, verifique si su segundo elemento está en la tabla hash. En caso afirmativo, compare el primer elemento con el valor de la entrada coincidente de la tabla hash. Si el valor y el primer elemento coinciden, encontramos pares simétricos. De lo contrario, inserte el primer elemento como clave y el segundo elemento como valor.
A continuación se muestra la implementación del enfoque anterior:
C++
#include<bits/stdc++.h>
using namespace std;
// A C++ program to find all symmetric pairs in a given array of pairs
// Print all pairs that have a symmetric counterpart
void findSymPairs(int arr[][2], int row)
{
// Creates an empty hashMap hM
unordered_map<int, int> hM;
// Traverse through the given array
for (int i = 0; i < row; i++)
{
// First and second elements of current pair
int first = arr[i][0];
int sec = arr[i][1];
// If found and value in hash matches with first
// element of this pair, we found symmetry
if (hM.find(sec) != hM.end() && hM[sec] == first)
cout << "(" << sec << ", " << first << ")" <<endl;
else // Else put sec element of this pair in hash
hM[first] = sec;
}
}
// Driver method
int main()
{
int arr[5][2];
arr[0][0] = 11; arr[0][1] = 20;
arr[1][0] = 30; arr[1][1] = 40;
arr[2][0] = 5; arr[2][1] = 10;
arr[3][0] = 40; arr[3][1] = 30;
arr[4][0] = 10; arr[4][1] = 5;
cout<<"Following pairs have symmetric pairs\n";
findSymPairs(arr, 5);
}
//This is contributed by Chhavi
Java
// A Java program to find all symmetric pairs in a given array of pairs
import java.util.HashMap;
class SymmetricPairs {
// Print all pairs that have a symmetric counterpart
static void findSymPairs(int arr[][])
{
// Creates an empty hashMap hM
HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();
// Traverse through the given array
for (int i = 0; i < arr.length; i++)
{
// First and second elements of current pair
int first = arr[i][0];
int sec = arr[i][1];
// Look for second element of this pair in hash
Integer val = hM.get(sec);
// If found and value in hash matches with first
// element of this pair, we found symmetry
if (val != null && val == first)
System.out.println("(" + sec + ", " + first + ")");
else // Else put sec element of this pair in hash
hM.put(first, sec);
}
}
// Driver method
public static void main(String arg[])
{
int arr[][] = new int[5][2];
arr[0][0] = 11; arr[0][1] = 20;
arr[1][0] = 30; arr[1][1] = 40;
arr[2][0] = 5; arr[2][1] = 10;
arr[3][0] = 40; arr[3][1] = 30;
arr[4][0] = 10; arr[4][1] = 5;
findSymPairs(arr);
}
}
Python3
# A Python3 program to find all symmetric
# pairs in a given array of pairs.
# Print all pairs that have
# a symmetric counterpart
def findSymPairs(arr, row):
# Creates an empty hashMap hM
hM = dict()
# Traverse through the given array
for i in range(row):
# First and second elements
# of current pair
first = arr[i][0]
sec = arr[i][1]
# If found and value in hash matches with first
# element of this pair, we found symmetry
if (sec in hM.keys() and hM[sec] == first):
print("(", sec,",", first, ")")
else: # Else put sec element of
# this pair in hash
hM[first] = sec
# Driver Code
if __name__ == '__main__':
arr = [[0 for i in range(2)]
for i in range(5)]
arr[0][0], arr[0][1] = 11, 20
arr[1][0], arr[1][1] = 30, 40
arr[2][0], arr[2][1] = 5, 10
arr[3][0], arr[3][1] = 40, 30
arr[4][0], arr[4][1] = 10, 5
findSymPairs(arr, 5)
# This code is contributed by Mohit Kumar
C#
// C# program to find all symmetric
// pairs in a given array of pairs
using System;
using System.Collections.Generic;
public class SymmetricPairs
{
// Print all pairs that have a symmetric counterpart
static void findSymPairs(int [,]arr)
{
// Creates an empty hashMap hM
Dictionary<int,int> hM = new Dictionary<int,int>();
int val = 0;
// Traverse through the given array
for (int i = 0; i < arr.GetLength(0); i++)
{
// First and second elements of current pair
int first = arr[i, 0];
int sec = arr[i, 1];
// Look for second element of this pair in hash
if(hM.ContainsKey(sec))
val = hM[sec];
// If found and value in hash matches with first
// element of this pair, we found symmetry
if (val != 0 && val == first)
Console.WriteLine("(" + sec + ", " + first + ")");
else // Else put sec element of this pair in hash
hM.Add(first, sec);
}
}
// Driver code
public static void Main(String []arg)
{
int [,]arr = new int[5, 2];
arr[0, 0] = 11; arr[0, 1] = 20;
arr[1, 0] = 30; arr[1, 1] = 40;
arr[2, 0] = 5; arr[2, 1] = 10;
arr[3, 0] = 40; arr[3, 1] = 30;
arr[4, 0] = 10; arr[4, 1] = 5;
findSymPairs(arr);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// A Javascript program to find all symmetric pairs in a given array of pairs
// Print all pairs that have a symmetric counterpart
function findSymPairs(arr)
{
// Creates an empty hashMap hM
let hM = new Map();
// Traverse through the given array
for (let i = 0; i < arr.length; i++)
{
// First and second elements of current pair
let first = arr[i][0];
let sec = arr[i][1];
// Look for second element of this pair in hash
let val = hM.get(sec);
// If found and value in hash matches with first
// element of this pair, we found symmetry
if (val != null && val == first)
document.write("(" + sec + ", " + first + ")<br>");
else // Else put sec element of this pair in hash
hM.set(first, sec);
}
}
// Driver method
let arr = new Array(5);
for(let i = 0; i < arr.length; i++)
{
arr[i] = new Array(2);
for(let j = 0; j < 2; j++)
{
arr[i][j] = 0;
}
}
arr[0][0] = 11; arr[0][1] = 20;
arr[1][0] = 30; arr[1][1] = 40;
arr[2][0] = 5; arr[2][1] = 10;
arr[3][0] = 40; arr[3][1] = 30;
arr[4][0] = 10; arr[4][1] = 5;
findSymPairs(arr);
// This code is contributed by unknown2108
</script>
Following pairs have symmetric pairs (30, 40) (5, 10)
Complejidad de tiempo: O(n), donde n es el tamaño de la array dada.
Espacio Auxiliar: O(n)
Este artículo es una contribución de Shivam Agrawal . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA