Dadas dos arrays no ordenadas, verifique si ambas arrays tienen el mismo conjunto de elementos o no.
Ejemplos:
Input : A = {2, 5, 6, 8, 10, 2, 2}
B = {2, 5, 5, 6, 8, 5, 6}
Output : No
Input : A = {2, 5, 6, 8, 2, 10, 2}
B = {2, 5, 6, 8, 2, 10, 2}
Output : Yes
Input : A = {2, 5, 8, 6, 10, 2, 2}
B = {2, 5, 6, 8, 2, 10, 2}
Output : Yes
Método 1 (simple):
una solución simple a este problema es verificar si cada elemento de A está presente en B. Pero este enfoque conducirá a una respuesta incorrecta en caso de que haya múltiples instancias de un elemento presente en B. Para superar esto problema, marcamos las instancias visitadas de B[] usando una array auxiliar visitada[].
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if both arrays are same
bool areSameSet(vector<int> A, vector<int> B)
{
int n = A.size();
if (B.size() != n)
return false;
// visited array is used to handle duplicates
vector<bool> visited(n, false);
// each element of A is matched
// against each element of B
for (int i = 0; i < n; i++) {
int j = 0;
for (j = 0; j < n; j++)
{
if (A[i] == B[j] && visited[j] == false)
{
visited[j] = true;
break;
}
}
// If we could not find A[i] in B[]
if (j == n)
return false;
}
return true;
}
// Driver code
int main()
{
vector<int> A, B;
A.push_back(2);
A.push_back(5);
A.push_back(10);
A.push_back(6);
A.push_back(8);
A.push_back(2);
A.push_back(2);
B.push_back(2);
B.push_back(5);
B.push_back(6);
B.push_back(8);
B.push_back(10);
B.push_back(2);
B.push_back(2);
areSameSet(A, B)? cout << "Yes" : cout << "No";
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG
{
// Function to check if both arrays are same
static boolean areSameSet(Vector<Integer> A, Vector<Integer> B)
{
int n = A.size();
if (B.size() != n)
{
return false;
}
// visited array is used to handle duplicates
Vector<Boolean> visited = new Vector<Boolean>();
for (int i = 0; i < n; i++)
{
visited.add(i, Boolean.FALSE);
}
// each element of A is matched
// against each element of B
for (int i = 0; i < n; i++)
{
int j = 0;
for (j = 0; j < n; j++)
{
if (A.get(i) == B.get(j) && visited.get(j) == false)
{
visited.add(j, Boolean.TRUE);
break;
}
}
// If we could not find A[i] in B[]
if (j == n)
{
return false;
}
}
return true;
}
// Driver code
public static void main(String[] args)
{
Vector<Integer> A = new Vector<>();
Vector<Integer> B = new Vector<>();
A.add(2);
A.add(5);
A.add(10);
A.add(6);
A.add(8);
A.add(2);
A.add(2);
B.add(2);
B.add(5);
B.add(6);
B.add(8);
B.add(10);
B.add(2);
B.add(2);
if (areSameSet(A, B))
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python3 implementation of the above approach
# Function to check if both arrays are same
def areSameSet(A, B):
n = len(A)
if (len(B) != n):
return False
# visited array is used to handle duplicates
visited = [False for i in range(n)]
# each element of A is matched
# against each element of B
for i in range(n):
j = 0
for j in range(n):
if (A[i] == B[j] and
visited[j] == False):
visited[j] = True
break
# If we could not find A[i] in B[]
if (j == n):
return False
return True
# Driver code
A = []
B = []
A.append(2)
A.append(5)
A.append(10)
A.append(6)
A.append(8)
A.append(2)
A.append(2)
B.append(2)
B.append(5)
B.append(6)
B.append(8)
B.append(10)
B.append(2)
B.append(2)
if(areSameSet(A, B)):
print("Yes")
else:
print("No")
# This code is contributed
# by mohit kumar
C#
// C# implementation of the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to check if both arrays are same
static Boolean areSameSet(List<int> A, List<int> B)
{
int n = A.Count;
if (B.Count != n)
{
return false;
}
// visited array is used to handle duplicates
List<Boolean> visited = new List<Boolean>();
for (int i = 0; i < n; i++)
{
visited.Insert(i, false);
}
// each element of A is matched
// against each element of B
for (int i = 0; i < n; i++)
{
int j = 0;
for (j = 0; j < n; j++)
{
if (A[i] == B[j] && visited[j] == false)
{
visited.Insert(j, true);
break;
}
}
// If we could not find A[i] in B[]
if (j == n)
{
return false;
}
}
return true;
}
// Driver code
public static void Main(String[] args)
{
List<int> A = new List<int>();
List<int> B = new List<int>();
A.Add(2);
A.Add(5);
A.Add(10);
A.Add(6);
A.Add(8);
A.Add(2);
A.Add(2);
B.Add(2);
B.Add(5);
B.Add(6);
B.Add(8);
B.Add(10);
B.Add(2);
B.Add(2);
if (areSameSet(A, B))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the above approach
// Function to check if both arrays are same
function areSameSet(A,B)
{
let n = A.length;
if (B.length != n)
{
return false;
}
// visited array is used to handle duplicates
let visited = [];
for (let i = 0; i < n; i++)
{
visited.push(false);
}
// each element of A is matched
// against each element of B
for (let i = 0; i < n; i++)
{
let j = 0;
for (j = 0; j < n; j++)
{
if (A[i] == B[j] && visited[j] == false)
{
visited[j]=true;
break;
}
}
// If we could not find A[i] in B[]
if (j == n)
{
return false;
}
}
return true;
}
// Driver code
let A=[];
let B=[];
A.push(2);
A.push(5);
A.push(10);
A.push(6);
A.push(8);
A.push(2);
A.push(2);
B.push(2);
B.push(5);
B.push(6);
B.push(8);
B.push(10);
B.push(2);
B.push(2);
if (areSameSet(A, B))
{
document.write("Yes");
}
else
{
document.write("No");
}
// This code is contributed by patel2127
</script>
Producción:
Yes
La complejidad temporal de la solución anterior en O(n^2).
Método 2 (Clasificación):
Ordene ambas arrays y compare los elementos correspondientes de cada array.
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if both arrays are same
bool areSameSet(vector<int> A, vector<int> B)
{
int n = A.size();
if (B.size() != n)
return false;
sort(A.begin(), A.end());
sort(B.begin(), B.end());
// Compare corresponding elements
for (int i = 0; i < n; i++)
if (A[i] != B[i])
return false;
return true;
}
int main()
{
vector<int> A, B;
A.push_back(2);
A.push_back(5);
A.push_back(10);
A.push_back(6);
A.push_back(8);
A.push_back(2);
A.push_back(2);
B.push_back(2);
B.push_back(5);
B.push_back(6);
B.push_back(8);
B.push_back(10);
B.push_back(2);
B.push_back(2);
areSameSet(A, B)? cout << "Yes" : cout << "No";
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to check if both arrays are same
static boolean areSameSet(Vector<Integer> A,
Vector<Integer> B)
{
int n = A.size();
if (B.size() != n)
{
return false;
}
Collections.sort(A);
Collections.sort(B);
// Compare corresponding elements
for (int i = 0; i < n; i++)
{
if (A.get(i) != B.get(i))
{
return false;
}
}
return true;
}
// Driver code
public static void main(String[] args)
{
Vector<Integer> A = new Vector<>();
Vector<Integer> B = new Vector<>();
A.add(2);
A.add(5);
A.add(10);
A.add(6);
A.add(8);
A.add(2);
A.add(2);
B.add(2);
B.add(5);
B.add(6);
B.add(8);
B.add(10);
B.add(2);
B.add(2);
if (areSameSet(A, B))
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach
# Function to check if
# both arrays are same
def areSameSet(A, B):
n = len(A)
if (len(B) != n):
return False
A.sort()
B.sort()
# Compare corresponding
# elements
for i in range (n):
if (A[i] != B[i]):
return False
return True
# Driver code
if __name__ == "__main__":
A = []
B = []
A.append(2)
A.append(5)
A.append(10)
A.append(6)
A.append(8)
A.append(2)
A.append(2)
B.append(2)
B.append(5)
B.append(6)
B.append(8)
B.append(10)
B.append(2)
B.append(2)
if areSameSet(A, B):
print ("Yes")
else:
print ("No")
# This code is contributed by Chitranayal
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to check if both arrays are same
static Boolean areSameSet(List<int> A,
List<int> B)
{
int n = A.Count;
if (B.Count!= n)
{
return false;
}
A.Sort();
B.Sort();
// Compare corresponding elements
for (int i = 0; i < n; i++)
{
if (A[i] != B[i])
{
return false;
}
}
return true;
}
// Driver code
public static void Main(String[] args)
{
List<int> A = new List<int>();
List<int> B = new List<int>();
A.Add(2);
A.Add(5);
A.Add(10);
A.Add(6);
A.Add(8);
A.Add(2);
A.Add(2);
B.Add(2);
B.Add(5);
B.Add(6);
B.Add(8);
B.Add(10);
B.Add(2);
B.Add(2);
if (areSameSet(A, B))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript implementation of the approach
// Function to check if both arrays are same
function areSameSet(A, B)
{
let n = A.length;
if (B.length != n)
{
return false;
}
A.sort(function(a, b){return a - b;});
B.sort(function(a, b){return a - b;});
// Compare corresponding elements
for(let i = 0; i < n; i++)
{
if (A[i] != B[i])
{
return false;
}
}
return true;
}
// Driver code
let A = [];
let B = [];
A.push(2);
A.push(5);
A.push(10);
A.push(6);
A.push(8);
A.push(2);
A.push(2);
B.push(2);
B.push(5);
B.push(6);
B.push(8);
B.push(10);
B.push(2);
B.push(2);
if (areSameSet(A, B))
{
document.write("Yes");
}
else
{
document.write("No");
}
// This code is contributed by unknown2108
</script>
Producción:
Yes
La complejidad temporal de la solución anterior es O(n*log(n)).
Método 3 (hashing):
podemos disminuir la complejidad temporal del problema anterior mediante el uso de una tabla Hash. Primero, iteramos a través de A y marcamos el número de instancias de cada elemento de A en una tabla hash. Luego iteramos a través de B y disminuimos el valor correspondiente en la tabla hash. Si al final si todas las entradas de la tabla hash son cero, la respuesta será «Sí», de lo contrario, «No».
C++
// C++ program to implement Naive approach
// to remove duplicates
#include <bits/stdc++.h>
using namespace std;
bool areSameSet(vector<int> A, vector<int> B)
{
int n = A.size();
if (B.size() != n)
return false;
// Create a hash table to
// number of instances
unordered_map<int> m;
// for each element of A
// increase it's instance by 1.
for (int i = 0; i < n; i++)
m[A[i]]++;
// for each element of B
// decrease it's instance by 1.
for (int i = 0; i < n; i++)
m[B[i]]--;
// Iterate through map and check if
// any entry is non-zero
for (auto i : m)
if (i.second != 0)
return false;
return true;
}
int main()
{
vector<int> A, B;
A.push_back(2);
A.push_back(5);
A.push_back(10);
A.push_back(6);
A.push_back(8);
A.push_back(2);
A.push_back(2);
B.push_back(2);
B.push_back(5);
B.push_back(6);
B.push_back(8);
B.push_back(10);
B.push_back(2);
B.push_back(2);
areSameSet(A, B)? cout << "Yes" : cout << "No";
}
Java
// Java program to implement Naive approach
// to remove duplicates
import java.util.HashMap;
class GFG
{
static boolean areSameSet(int[] A, int[] B)
{
int n = A.length;
if (B.length != n)
return false;
// Create a hash table to
// number of instances
HashMap<Integer,
Integer> m = new HashMap<>();
// for each element of A
// increase it's instance by 1.
for (int i = 0; i < n; i++)
m.put(A[i], m.get(A[i]) == null ? 1 :
m.get(A[i]) + 1);
// for each element of B
// decrease it's instance by 1.
for (int i = 0; i < n; i++)
m.put(B[i], m.get(B[i]) - 1);
// Iterate through map and check if
// any entry is non-zero
for (HashMap.Entry<Integer,
Integer> entry : m.entrySet())
if (entry.getValue() != 0)
return false;
return true;
}
// Driver Code
public static void main(String[] args)
{
int[] A = { 2, 5, 10, 6, 8, 2, 2 };
int[] B = { 2, 5, 6, 8, 10, 2, 2 };
if (areSameSet(A, B))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 program to implement Naive
# approach to remove duplicates
def areSameSet(A, B):
n = len(A)
if (len(B) != n):
return False
# Create a hash table to
# number of instances
m = {}
# For each element of A
# increase it's instance by 1.
for i in range(n):
if A[i] not in m:
m[A[i]] = 1
else:
m[A[i]] += 1
# For each element of B
# decrease it's instance by 1.
for i in range(n):
if B[i] in m:
m[B[i]] -= 1
# Iterate through map and check if
# any entry is non-zero
for i in m:
if (m[i] != 0):
return False
return True
# Driver Code
A = []
B = []
A.append(2)
A.append(5)
A.append(10)
A.append(6)
A.append(8)
A.append(2)
A.append(2)
B.append(2)
B.append(5)
B.append(6)
B.append(8)
B.append(10)
B.append(2)
B.append(2)
if (areSameSet(A, B)):
print("Yes")
else:
print("No")
# This code is contributed by avanitrachhadiya2155
C#
// C# program to implement Naive approach
// to remove duplicates
using System;
using System.Collections.Generic;
class GFG
{
static bool areSameSet(int[] A, int[] B)
{
int n = A.Length;
if (B.Length != n)
return false;
// Create a hash table to
// number of instances
Dictionary<int,int> m = new Dictionary<int,int>();
// for each element of A
// increase it's instance by 1.
for (int i = 0; i < n; i++)
if(m.ContainsKey(A[i]))
m[A[i]] = m[A[i]] + 1;
else
m.Add(A[i], 1);
// for each element of B
// decrease it's instance by 1.
for (int i = 0; i < n; i++)
if(m.ContainsKey(B[i]))
m[B[i]] = m[B[i]] - 1;
// Iterate through map and check if
// any entry is non-zero
foreach(KeyValuePair<int, int> entry in m)
if (entry.Value != 0)
return false;
return true;
}
// Driver Code
public static void Main(String[] args)
{
int[] A = { 2, 5, 10, 6, 8, 2, 2 };
int[] B = { 2, 5, 6, 8, 10, 2, 2 };
if (areSameSet(A, B))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to implement Naive approach
// to remove duplicates
function areSameSet(A,B)
{
let n = A.length;
if (B.length != n)
return false;
// Create a hash table to
// number of instances
let m = new Map();
// for each element of A
// increase it's instance by 1.
for (let i = 0; i < n; i++)
m.set(A[i], m.get(A[i]) == null ? 1 :
m.get(A[i]) + 1);
// for each element of B
// decrease it's instance by 1.
for (let i = 0; i < n; i++)
m.set(B[i], m.get(B[i]) - 1);
// Iterate through map and check if
// any entry is non-zero
for (let [key, value] of m.entries())
if (value != 0)
return false;
return true;
}
// Driver Code
let A=[2, 5, 10, 6, 8, 2, 2 ];
let B=[2, 5, 6, 8, 10, 2, 2];
if (areSameSet(A, B))
document.write("Yes");
else
document.write("No");
// This code is contributed by rag2127
</script>
Producción:
Yes
La complejidad temporal del método anterior es O(n).
Este artículo es una contribución de Raghav Sharma . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuir@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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