A diferencia de un conjunto, un conjunto múltiple puede contener múltiples ocurrencias del mismo número. El problema de equivalencia de conjuntos múltiples establece verificar si dos conjuntos múltiples dados son iguales o no. Por ejemplo, sea A = {1, 2, 3} y B = {1, 1, 2, 3}. Aquí A está establecido pero B no (1 aparece dos veces en B), mientras que A y B son ambos conjuntos múltiples. Más formalmente, «¿Se definen los conjuntos
de pares como iguales para los dos multiconjuntos dados?»
Dados dos conjuntos múltiples A y B, escriba un programa para verificar si los dos conjuntos múltiples son iguales.
Nota : Los elementos de los conjuntos múltiples pueden ser del orden 10 9
Ejemplos:
Input : A = {1, 1, 3, 4},
B = {1, 1, 3, 4}
Output : Yes
Input : A = {1, 3},
B = {1, 1}
Output : No
Dado que los elementos son tan grandes como 10 ^ 9, no podemos usar la tabla de índice directo .
Una solución es ordenar ambos conjuntos múltiples y compararlos uno por uno.
C++
// C++ program to check if two given multisets
// are equivalent
#include <bits/stdc++.h>
using namespace std;
bool areSame(vector<int>& a, vector<int>& b)
{
// sort the elements of both multisets
sort(a.begin(), a.end());
sort(b.begin(), b.end());
// Return true if both multisets are same.
return (a == b);
}
int main()
{
vector<int> a({ 7, 7, 5 }), b({ 7, 5, 5 });
if (areSame(a, b))
cout << "Yes\n";
else
cout << "No\n";
return 0;
}
Java
// Java program to check if two given multisets
// are equivalent
import java.util.*;
class GFG {
static boolean areSame(Vector<Integer>a, Vector<Integer>b)
{
// sort the elements of both multisets
Collections.sort(a);
Collections.sort(b);
// Return true if both multisets are same.
return (a == b);
}
public static void main(String[] args) {
Vector<Integer> a = new Vector<Integer>(Arrays.asList( 7, 7, 5 ));
Vector<Integer> b = new Vector<Integer>(Arrays.asList( 7, 5, 5));
if (areSame(a, b))
System.out.print("Yes\n");
else
System.out.print("No\n");
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to check if
# two given multisets are equivalent
def areSame(a, b):
# sort the elements of both multisets
a.sort();
b.sort();
# Return true if both multisets are same.
return (a == b);
# Driver Code
a = [ 7, 7, 5 ];
b = [ 7, 5, 5 ];
if (areSame(a, b)):
print("Yes");
else:
print("No");
# This code is contributed by Princi Singh
C#
// C# program to check if two given multisets
// are equivalent
using System;
using System.Collections.Generic;
class GFG
{
static bool areSame(List<int>a, List<int>b)
{
// sort the elements of both multisets
a.Sort();
b.Sort();
// Return true if both multisets are same.
return (a == b);
}
// Driver code
public static void Main()
{
List<int> a = new List<int> { 7, 7, 5 };
List<int> b = new List<int> { 7, 5, 5 };
if (areSame(a, b))
Console.WriteLine("Yes\n");
else
Console.WriteLine("No\n");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to check if two given multisets
// are equivalent
function areSame(a, b) {
// sort the elements of both multisets
a.sort((a, b) => a - b);
b.sort((a, b) => a - b);
// Return true if both multisets are same.
return (a == b);
}
let a = [7, 7, 5], b = [7, 5, 5];
if (areSame(a, b))
document.write("Yes<br>");
else
document.write("No<br>");
</script>
Producción:
No
Complejidad de tiempo : O(n*log(n))
Espacio auxiliar : O(1)
Una mejor solución es usar hashing. Creamos dos tablas hash vacías (implementadas usando unordered_map en C++ ). Primero insertamos todos los elementos del primer mapa múltiple en la primera tabla y todos los elementos del segundo conjunto múltiple en la segunda tabla. Ahora comprobamos si ambas tablas hash contienen los mismos elementos y frecuencias o no.
C++
// C++ program to check if two given multisets
// are equivalent
#include <bits/stdc++.h>
using namespace std;
bool areSame(vector<int>& a, vector<int>& b)
{
if (a.size() != b.size())
return false;
// Create two unordered maps m1 and m2
// and insert values of both vectors.
unordered_map<int, int> m1, m2;
for (int i = 0; i < a.size(); i++) {
m1[a[i]]++;
m2[b[i]]++;
}
// Now we check if both unordered_maps
// are same of not.
for (auto x : m1) {
if (m2.find(x.first) == m2.end() ||
m2[x.first] != x.second)
return false;
}
return true;
}
// Driver code
int main()
{
vector<int> a({ 7, 7, 5 }), b({ 7, 7, 5 });
if (areSame(a, b))
cout << "Yes\n";
else
cout << "No\n";
return 0;
}
Java
// Java program to check if two given multisets
// are equivalent
import java.util.*;
class GFG
{
static boolean areSame(int []a, int []b)
{
if (a.length != b.length)
return false;
// Create two unordered maps m1 and m2
// and insert values of both vectors.
HashMap<Integer, Integer> m1, m2;
m1 = new HashMap<Integer, Integer>();
m2 = new HashMap<Integer, Integer>();
for (int i = 0; i < a.length; i++)
{
if(m1.containsKey(a[i]))
{
m1.put(a[i], m1.get(a[i]) + 1);
}
else
{
m1.put(a[i], 1);
}
if(m2.containsKey(b[i]))
{
m2.put(b[i], m2.get(b[i]) + 1);
}
else
{
m2.put(b[i], 1);
}
}
// Now we check if both unordered_maps
// are same of not.
for (Map.Entry<Integer, Integer> x : m1.entrySet())
{
if (!m2.containsKey(x.getKey()) ||
m2.get(x.getKey()) != x.getValue())
return false;
}
return true;
}
// Driver code
public static void main(String args[])
{
int []a = { 7, 7, 5 };
int []b = { 7, 7, 5 };
if (areSame(a, b))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program to check if two given multisets
# are equivalent
def areSame(a, b):
if (len(a) != len(b)):
return False
# Create two unordered maps m1 and m2
# and insert values of both vectors.
m1 = {}
m2 = {}
for i in range(len(a)):
if (a[i] in m1):
m1[a[i]] = m1[a[i]] + 1
else:
m1[a[i]] = 1
if (b[i] in m2):
m2[b[i]] = m2[b[i]] + 1
else:
m2[b[i]] = 1
# Now we check if both unordered_maps
# are same of not.
for k in m1.keys():
if (k not in m1 or m2[k] != m1[k]):
return False
return True
# Driver code
a = [7, 7, 5]
b = [7, 7, 5]
if (areSame(a, b)):
print("Yes")
else:
print("No")
# This code is contributed by Saurabh Jaiswal
C#
// C# program to check if two given multisets
// are equivalent
using System;
using System.Collections.Generic;
class GFG
{
static bool areSame(int []a, int []b)
{
if (a.Length != b.Length)
return false;
// Create two unordered maps m1 and m2
// and insert values of both vectors.
Dictionary<int, int> m1, m2;
m1 = new Dictionary<int, int>();
m2 = new Dictionary<int, int>();
for (int i = 0; i < a.Length; i++)
{
if(m1.ContainsKey(a[i]))
{
m1[a[i]] = m1[a[i]] + 1;
}
else
{
m1.Add(a[i], 1);
}
if(m2.ContainsKey(b[i]))
{
m2[b[i]] = m2[b[i]] + 1;
}
else
{
m2.Add(b[i], 1);
}
}
// Now we check if both unordered_maps
// are same of not.
foreach(KeyValuePair<int, int> x in m1)
{
if (!m2.ContainsKey(x.Key) ||
m2[x.Key] != x.Value)
return false;
}
return true;
}
// Driver code
public static void Main(String []args)
{
int []a = { 7, 7, 5 };
int []b = { 7, 7, 5 };
if (areSame(a, b))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to check if two given multisets
// are equivalent
function areSame(a, b)
{
if (a.length != b.length) return false;
// Create two unordered maps m1 and m2
// and insert values of both vectors.
var m1, m2;
m1 = {};
m2 = {};
for (var i = 0; i < a.length; i++)
{
if (m1.hasOwnProperty(a[i]))
{
m1[a[i]] = m1[a[i]] + 1;
} else {
m1[a[i]] = 1;
}
if (m2.hasOwnProperty(b[i])) {
m2[b[i]] = m2[b[i]] + 1;
} else {
m2[b[i]] = 1;
}
}
// Now we check if both unordered_maps
// are same of not.
for (const [key, value] of Object.entries(m1)) {
if (!m2.hasOwnProperty(key) || m2[key] != value) return false;
}
return true;
}
// Driver code
var a = [7, 7, 5];
var b = [7, 7, 5];
if (areSame(a, b)) document.write("Yes");
else document.write("No");
// This code is contributed by rdtank.
</script>
Producción:
Yes
Complejidad de tiempo: O(n) bajo el supuesto de que las operaciones find() e insert() de unordered_map funcionan en tiempo O(1).
Espacio Auxiliar : O(n)
Publicación traducida automáticamente
Artículo escrito por TuhinPatra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA